題目大意:

我們需要將一串數字分成多個確定個數的連續段，在得到所有段的和的最大值

?

定義一個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; }

?

轉載于:https://www.cnblogs.com/CSU3901130321/p/4184591.html

總結

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

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