STEP5 0006 Ch1-3.陷阱

[DP?]
應該算DP 反正就是每次搬過去後其實不需要重算的概念

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#define ULLI  long long int
ULLI max(ULLI a,ULLI b){if(a>b)return a;return b;}
ULLI min(ULLI a,ULLI b){if(a<b)return a;return b;}
ULLI a[1000000];
int main()
{
    int T;scanf("%d",&T);
    for(int lT=1;lT<=T;lT++)
    {
        int n;scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(int lx=0;lx<n;lx++)
            scanf("%I64u",&a[lx]);
        ULLI spend=0;ULLI sum=0;
        for(int lx=0;lx<n;lx++)
        {
            sum+=a[lx];
            if(sum<=0)
            {
                spend+=-sum+1;
                sum=1;
            }
        }
        ULLI mm=spend;
        for(int lx=n-1;lx>0;lx--)
        {
            if(a[lx]<=0)
                spend+=-a[lx];
            else
                spend=max(0,spend-a[lx]);
            mm=min(spend+n-lx,mm);
        }
        printf("%I64u\n",mm);
    }
    return 0;
}