首页 > 代码库 > HDU 1244 DP
HDU 1244 DP
题目大意:
我们需要将一串数字分成多个确定个数的连续段，在得到所有段的和的最大值
定义一个dp[i][j]数组表示在前j个数中取满 i 个段所能得到的最大值
那么也就是说明在这道题目当中每一段都是必须要被取到的
能够取到的前提是 j >= cnt[i] //表示前 i 段的数字个数总和
sum[i] 表示前 i 个数字之和
我们可以分成两种情况，一种是第i段取到以j号数字结尾
得到dp[i-1][j-l[i]] + sum[j] - sum[j-l[i]]
第二种是不以j号数字结尾
得到dp[i][j-1]
我们每次在其中取最大值就好了
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int INF = 200000000;const int M = 22;const int N = 1005;int dp[M][N] , l[M] , a[N] , cnt[M] , sum[N];int main(){ int m , n; while(scanf("%d" , &n) , n){ scanf("%d" , &m); for(int i = 1 ; i<=m ; i++){ scanf("%d" , l+i); cnt[i] = cnt[i-1] + l[i]; } for(int i = 1 ; i<= n ; i++){ scanf("%d" , a+i); sum[i] = sum[i-1] + a[i]; } memset(dp , 0 , sizeof(dp)); /* 第一次用这个交为了防止结果允许为负数的情况，可以AC 但是只是简单的dp初始为0，也没问题，个人感觉题目不是出的很严格 for(int i = 1 ; i<= m ; i++) for(int j = cnt[i] ; j<=n ; j++) dp[i][j] = -INF; */ for(int i = 1 ; i<= m ; i++) for(int j = cnt[i] ; j<=n ; j++){ dp[i][j] = max(dp[i-1][j-l[i]] + sum[j] - sum[j-l[i]] , dp[i][j-1]); } printf("%d\n" , dp[m][n]); } return 0;}
HDU 1244 DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。