1976.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<string.h>
#define debug 0
#define NMAX 10002
int a[NMAX];
int s[4][NMAX];

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("%d\n",s[3][N]);
        
    }
#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}