[HDU4223] 최소 하위 시퀀스 및 절대 값

3709 단어
동적 기획의 해법이 떠오르지 않아서...
마지막으로 구간과...
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>

int res;
using namespace std;
int main()
{
    int t,m;
    int a[100000],sum[100000];
    scanf("%d",&t);
    for(int cnt=1;cnt<=t;cnt++){
        scanf("%d",&m);
        res = 100000000;
        sum[0] = 0;
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++){
            sum[i] = a[i-1] + sum[i-1];
            if(res>abs(sum[i])){
                res = abs(sum[i]);
            }
        }
        for(int i=2;i<=m;i++){
            for(int j = 1;j<i;j++){
                if(res>abs(sum[i]-sum[j])){
                    res = abs(sum[i]-sum[j]);
                }
            }
        }
        printf("Case %d: %d
",cnt,res); } return 0; }

좋은 웹페이지 즐겨찾기