HDU 1244最大mセグメント連続サブストリング問題
1835 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1244
Problem Description
n個の正の整数からなる整数シーケンスを与える
a1 a2 a3 ... an
mセグメントの長さがそれぞれl 1、l 2、l 3...lmの重ならない連続整数の和の最大値を前後順にとる.
Input
1行目は整数n(0≦n≦1000)であり、n=0は入力終了を示す
2行目の最初の数はm(1≦m≦20)であり、
2行目には、次にm個の整数l 1,l 2...lmがあります.
3行目はn個の整数a 1,a 2,a 2...anである.
Output
mセグメントの整数和の最大値を出力します.
Sample Input
Sample Output
Problem Description
n個の正の整数からなる整数シーケンスを与える
a1 a2 a3 ... an
mセグメントの長さがそれぞれl 1、l 2、l 3...lmの重ならない連続整数の和の最大値を前後順にとる.
Input
1行目は整数n(0≦n≦1000)であり、n=0は入力終了を示す
2行目の最初の数はm(1≦m≦20)であり、
2行目には、次にm個の整数l 1,l 2...lmがあります.
3行目はn個の整数a 1,a 2,a 2...anである.
Output
mセグメントの整数和の最大値を出力します.
Sample Input
3
2 1 1
1 2 3
4
2 1 2
1 2 3 5
0
Sample Output
5
10
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int a[1005],b[1005],dp[1005][1005],num[1005];
int main()
{
int m,n;
while(~scanf("%d%d",&n,&m))
{
if(n==0)
break;
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
num[i]=num[i-1]+a[i];// i ;
for(int i=1;i<=n;i++)// ( )
for(int j=1;j<=m;j++)//
{
dp[i][j]=dp[i-1][j];// i b[j] i-1 j
if(i>=b[j])
dp[i][j]=max(dp[i-1][j],dp[i-b[j]][j-1]+num[i]-num[i-b[j]]);/* (1)i-1 j (2)i-b[j] j+1 num[i]-num[i-b[j]] */
}
printf("%d
",dp[n][m]);
}
return 0;
}