題意：求m個不相交區間段的和的和的和最大 思路：動態規劃 分析：dp[i][j]表示以a[j]結尾的i個區間段的和的最大和； 狀態轉移方程：dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]) dp[i-1][k]=max(dp[i-1][i~n]) 即劃分成i-1個區間分別以（a[i~n]）為結尾中的最大值。（當劃分成i個區間的時候前1-i個數字必定在一個區間里） dp[i][j]可以表示為和上一個區間相連即dp[i][j-1]+a[j]或者自己獨立為一個區間即dp[i-1][k]+a[j]；
#include<iostream>#include<string>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>#include<cmath>#include<math.h>#include<vector>#include<map>#include<stack>using namespace std;typedef long long ll;#define INF 0x7fffffffint a[1000005];int dp[1000005];int PRe[1000005];int main(){ int n, m; while (scanf("%d %d", &m, &n) != EOF) { int maxx; memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp)); memset(pre, 0, sizeof(pre)); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= m; i++) { maxx = -INF; for (int j = i; j <= n; j++) { dp[j] = max(dp[j - 1] + a[j], pre[j - 1] + a[j]); pre[j - 1] = maxx;//記錄前面的最大值 maxx = max(dp[j], maxx);//更新到當前的最大值 } } printf("%d/n", maxx); } return 0;}鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1024
新聞熱點
疑難解答
