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

   
   
   
   
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; }