Max Sum Plus Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 932 Accepted Submission(s): 462
Problem Description
給定一個由n個正整數組成的整數序列
a1 a2 a3 ... an
求按先後次序在其中取m段長度分別為l1、l2、l3...lm的不交疊的連續整數的和的最大值。
Input
第一行是一個整數n(0 ≤ n ≤ 1000)，n = 0表示輸入結束
第二行的第一個數是m(1 ≤ m ≤ 20)，
第二行接下來有m個整數l1，l2...lm。
第三行是n個整數a1, a2, a2 ... an.
Output
輸出m段整數和的最大值。
Sample Input
3
2 1 1
1 2 3
4
2 1 2
1 2 3 5
0[cpp]
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 1010 #define M 21 int f[2][N],a[N],b[M]; int main(){ int i,j,k,l,n,m,T; while(scanf("%d",&n)&&n){ scanf("%d",&m); a[0]=b[0]=0; for(i=1;i<=m;i++)scanf("%d",&b[i]); for(i=1;i<=n;i++){ scanf("%d",&k); a[i]=a[i-1]+k; } //由於輸入的是正整數，和是遞增的，可得f[i][j]=max(f[i][j],f[i-1][j-b[i]]+sum[j-b[i]+1,j] memset(f,0,sizeof(f)); k=0;l=1; for(i=1;i<=m;i++){ for(j=b[i];j<=n;j++){//第j個放第i組 f[l][j]=max(f[l][j],f[l][j-1]); f[l][j]=max(f[l][j],f[k][j-b[i]]-a[j-b[i]]+a[j]); } l^=1;k^=1; } printf("%d\n",f[k][n]); } return 0; } #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1010
#define M 21
int f[2][N],a[N],b[M];
int main(){
int i,j,k,l,n,m,T;
while(scanf("%d",&n)&&n){
scanf("%d",&m);
a[0]=b[0]=0;
for(i=1;i<=m;i++)scanf("%d",&b[i]);
for(i=1;i<=n;i++){
scanf("%d",&k);
a[i]=a[i-1]+k;
}
//由於輸入的是正整數，和是遞增的，可得f[i][j]=max(f[i][j],f[i-1][j-b[i]]+sum[j-b[i]+1,j]
memset(f,0,sizeof(f));
k=0;l=1;
for(i=1;i<=m;i++){
for(j=b[i];j<=n;j++){//第j個放第i組
f[l][j]=max(f[l][j],f[l][j-1]);
f[l][j]=max(f[l][j],f[k][j-b[i]]-a[j-b[i]]+a[j]);
}
l^=1;k^=1;
}
printf("%d\n",f[k][n]);
}
return 0;
}
