Poj Solution 1976

http://poj.org/problem?id=1976

#include<stdio.h>
#include<string.h>

#define debug 0
#define NMAX 10002
int a[NMAX];
int s[4][NMAX];

int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int i,j,k,t,d,N;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&N);
        memset(s,0,sizeof(int));
        memset(a,0,sizeof(int));
        for(i=1;i<=N;i++)
        {
            scanf("%d",&a[i]);
            a[i]+=a[i-1];
        }
        scanf("%d",&d);
        for(k=1;k<=3;k++)
        {
            for(i=1;i<=N;i++)
            {
                j=0>i-d?0:i-d;
                s[k][i]=s[k][i-1]>s[k-1][j]+a[i]-a[j]?s[k][i-1]:s[k-1][j]+a[i]-a[j];
            }
        }
        
        printf("%dn",s[3][N]);
        
    }
#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *