雖然這道題看起來和 HDU 1024??Max Sum Plus Plus 看起來很像，可是感覺這道題比1024要簡單一些

前面WA了幾次，因為我開始把dp[22][maxn]寫成dp[maxn][22]了，Orz

看來數組越界不一定會導致程序崩潰，也有可能返回一個錯誤的結果

?

dp[i][j]表示前j個數構成前i段所得到的最大值

狀態轉移方程：

dp[i][j] = max{dp[i][j-1], ?dp[i-1][j-len[i]] + sum[j] - sum[j-len[i]]}

分別對應著不取第i個數和取第j個數及其之前相鄰的共len[i]個數作為第i段加上之前的數構成i-1段構成的最大值

?

1 //#define LOCAL 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1000 + 10; 8 int a[maxn], sum[maxn], len[22], dp[22][maxn]; 9 10 int main(void) 11 { 12 #ifdef LOCAL 13 freopen("1244in.txt", "r", stdin); 14 #endif 15 16 int n, m; 17 while(scanf("%d", &n) == 1 && n) 18 { 19 scanf("%d", &m); 20 for(int i = 1; i <= m; ++i) 21 scanf("%d", &len[i]); 22 for(int i = 1; i <= n; ++i) 23 scanf("%d", &a[i]); 24 sum[0] = 0; 25 for(int i = 1; i <= n; ++i) 26 sum[i] = sum[i - 1] + a[i]; 27 memset(dp, 0, sizeof(dp)); 28 for(int i = 1; i <= m; ++i) 29 { 30 for(int j = 1; j < len[i]; ++j) 31 dp[i][j] = dp[i][j-1]; 32 for(int j = len[i]; j <= n; ++j) 33 dp[i][j] = max(dp[i][j-1], dp[i-1][j-len[i]] + sum[j] - sum[j-len[i]]); 34 } 35 printf("%d\n", dp[m][n]); 36 } 37 return 0; 38 } 代碼君

?

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/3931550.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的HDU 1244 Max Sum Plus Plus Plus的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。