首页 > 其他 > 详细

HDU - 1244 - Max Sum Plus Plus Plus

时间:2014-04-13 14:26:29      阅读:430      评论:0      收藏:0      [点我收藏+]

先上题目

Max Sum Plus Plus Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1186    Accepted Submission(s): 591


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
 

 

Sample Output
5
10
 
  中文题意不解释,这题可以像背包问题那样解。
  dp[i][j]表示前j个数中分成i段可以得到的最大值。
  sum[i]表示前i个数的最大值。
  状态转移方程:dp[i][j]=max( dp[i][j-1] , dp[i-1][j-l[i]] + ( sum[j]-sum[j-l[i]] ) )
  意思就是如果不选a[j],那么dp[i][j]=dp[i][j-1],如果选a[j],d[i][j]=dp[i-1][j-l[i]]+(sum[j]-sum[j-l[i]])
  详细的分析还需要再搞懂一点才可以写。
 
上代码:
 
bubuko.com,布布扣
 1 #include <cstdio>
 2 #include <cstring>
 3 #define max(x,y) (x >= y ? x : y)
 4 #define MAX 1002
 5 #define LL long long
 6 using namespace std;
 7 
 8 LL a[MAX],sum[MAX],l[22];
 9 LL dp[22][MAX];
10 
11 int main()
12 {
13     int n,m,st;
14     //freopen("data.txt","r",stdin);
15     while(scanf("%d",&n),n){
16         scanf("%d",&m);
17         for(int i=1;i<=m;i++) scanf("%I64d",&l[i]);
18         sum[0]=0;
19         for(int i=1;i<=n;i++){
20             scanf("%I64d",&a[i]);
21             sum[i]=sum[i-1]+a[i];
22         }
23         memset(dp,0,sizeof(dp));
24         st=0;
25         for(int i=1;i<=m;i++){
26             st+=l[i];
27             for(int j=st;j<=n;j++){
28                 dp[i][j]=max(dp[i][j-1],dp[i-1][j-l[i]]+(sum[j]-sum[j-l[i]]));
29             }
30         }
31         printf("%I64d\n",dp[m][n]);
32     }
33     return 0;
34 }
1244

 

 
 

HDU - 1244 - Max Sum Plus Plus Plus,布布扣,bubuko.com

HDU - 1244 - Max Sum Plus Plus Plus

原文:http://www.cnblogs.com/sineatos/p/3660226.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!