hdu 4223 Dynamic Programming?(最小连续子序列绝对值和)

http://acm.hdu.edu.cn/showproblem.php?pid=4223

求连续子序列之和的绝对值最小值

这题做的真失败，不知道为什么用dp[i]表示到i为止绝对值最小值，WA了n次。直接暴力吧，

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
int ans;
int main()
{
    int test;
    scanf("%d",&test);
    for(int item = 1; item <= test; item++)
    {
        int n,a[1010];
        scanf("%d",&n);
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);

		ans = abs(a[1]);

		for(int i = 1; i <= n; i++)
		{
			int sum = 0;
			for(int j = i; j <= n; j++)
			{
				sum += a[j];
				if(ans > abs(sum))
					ans = abs(sum);
			}
		}
		printf("Case %d: %d\n",item,ans);
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
int ans;
int main()
{
    int test;
	int n,a[1010],sum[1010];

    scanf("%d",&test);
    for(int item = 1; item <= test; item++)
    {
        scanf("%d",&n);
        ans = INF;
        sum[0] = 0;	
        for(int i = 1; i <= n; i++)
		{
			scanf("%d",&a[i]);
			sum[i] = sum[i-1]+a[i]; // 1~i的和
			if(ans > abs(sum[i]))
				ans = abs(sum[i]);
		}

		for(int i = 2; i <= n; i++)
		{
			for(int j = 1; j < i; j++)
			{ //枚举区间的端点，求绝对值最小的
				if(ans > abs(sum[i]-sum[j]))
					ans = abs(sum[i]-sum[j]);
			}
		}

		printf("Case %d: %d\n",item,ans);
    }
    return 0;
}

hdu 4223 Dynamic Programming?(最小连续子序列绝对值和),布布扣,bubuko.com

hdu 4223 Dynamic Programming?(最小连续子序列绝对值和)

原文：http://blog.csdn.net/u013081425/article/details/20283045