A Mini Locomotive(动态规划 01)

 /*
 题意:选出3个连续的 数的个数  为K的区间,使他们的和最大
分析: dp[j][i]=max(dp[j-k][i-1]+value[j],dp[j-1][i]);
 
dp[j][i]:从j个数种选出i个连续区间  数值的最大和
value[j]:第j个区间内的数的和
和背包有点像,但要活用
 
*/
 
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[50005][4];
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
 
 
 
        int n;
        scanf("%d",&n);
        int a[n+1],sum[n+1];
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
 
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];//前缀和,用于求连续k个数的和
        }
 
 
 
        int k=0;
        scanf("%d",&k);
        int value[n+1];
        memset(value,0,sizeof(value));
        for(int i=1; i<=k; i++)
            value[i]=value[i-1]+a[i];
        for(int i=k+1; i<=n; i++)
            value[i]=sum[i]-sum[i-k];//连续k个数的和,value[i]代表区间长度为k的第i个区间
 
 
 
        for(int j=k; j<=n; j++)
            for(int i=1; i<=3; i++)
                dp[j][i]=max(dp[j-k][i-1]+value[j],dp[j-1][i]);//从j个数中选出i个区间,若选第i个区间,就相当于从前(j-k)个数中选出(i-1)个区间的基础上再加此区间(value[j]),若不选就是相当于在(j-1)个数中选i个区间
 
 
 
            printf("%d\n",dp[n][3]);
 
 
 
    }
 
    return 0;
}
上一篇:【spring 3】AOP:静态代理


下一篇:(转)winform之ListView