1244.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<iostream>
#include<string>
using namespace std;
int n,m,lensum,tmax,result;
int len[21]={0},a[1001]={0},numsum[1001]={0};
int dp[21][1001]={0};
int max(int a,int b){
    return a>b?a:b;
}
void main()
{
    int i,j;
    while(cin>>n,n){
        cin>>m;
        for(i=0;i<=n;i++)
            dp[0][i]=0;
        for(i=1;i<=m;i++)
            cin>>len[i];
        for(i=1;i<=n;i++){
            cin>>a[i];
            numsum[i]=numsum[i-1]+a[i];
        }
        lensum=0;
        for(i=1;i<=m;i++){
            tmax=numsum[lensum];
            for(j=lensum+len[i];j<=n;j++){
                tmax=max(tmax,dp[i-1][j-len[i]]);
                dp[i][j]=tmax+numsum[j]-numsum[j-len[i]];
            }
            lensum+=len[i];
        }
        result=numsum[lensum];
        for(i=lensum+1;i<=n;i++)
            result=max(result,dp[m][i]);
        cout<<result<<endl;
    }
}