首页 > ACM题库 > HDU-杭电 > HDU 4223- Dynamic Programming?-动态规划-[解题报告]HOJ
2015
05-23

HDU 4223- Dynamic Programming?-动态规划-[解题报告]HOJ

Dynamic Programming?

问题描述 :

Dynamic Programming, short for DP, is the favorite of iSea. It is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems which are only slightly smaller and optimal substructure.
Ok, here is the problem. Given an array with N integers, find a continuous subsequence whose sum’s absolute value is the smallest. Very typical DP problem, right?

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then a line with N integers Ai follows.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 1 000
3. -100 000 <= Ai <= 100 000

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then a line with N integers Ai follows.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 1 000
3. -100 000 <= Ai <= 100 000

样例输入:

2
2
1 -1
4
1 2 1 -2

样例输出:

Case 1: 0
Case 2: 1

点击打开链接

题意:

给你一n个数,有正有负,求连续的的最小绝对值

因为数据1000*1000完全可以暴力

dp[i]=min(dp[i],abs(sum(A[j],A[i])))

后者:j到i的数字和的绝对值

#include"stdio.h"
#include"string.h"
#define N 1101

int abs(int a)
{
	if(a>0)return a;
	return -a;
}

int main()
{
	int T;
	int n;
	int A[N];
	int dp[N];
	int i,j,t;
	int ans,cnt;

	scanf("%d",&T);
	cnt=1;
	while(T--)
	{
		scanf("%d",&n);
		scanf("%d",&A[0]);
		ans=dp[0]=abs(A[0]);
		for(i=1;i<n;i++)
		{
			scanf("%d",&A[i]);
			dp[i]=abs(A[i]);
			t=A[i];
			//因为要求是连续的,所以得从i-1开始
			for(j=i-1;j>=0;j--)
			{
				t+=A[j];
				if(abs(t)<dp[i])
					dp[i]=abs(t);
			}
			if(dp[i]<ans)ans=dp[i];
		}
		printf("Case %d: %d\n",cnt++,ans);
	}
	return 0;
}
		

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yangyafeiac/article/details/9613505