題意：
? ? ?給你一個序列n個數組成，然后讓你在里面找到m個子序列，讓這m個子序列的和最大。


思路：
? ? ? dp[i][j]表示的是第j個數字在第i個子序列時的當前最優值。
dp[i][j] = maxx(dp[i][j-1] + num[j] ,maxx(dp[i-1][k]) + num[j]); ?k是從1到j-1.

可以這么理解這個轉移方程，對于當前的這個數字，如果把他放到第i個子序列中有兩種情況，一個是他作為第i個子序列的第一個數字，另一個就是不作為第一個數字，作為第一個數字的時候是 maxx(dp[i-2][k] + num[j]) 1<=k<i 的意思是從之前的所有中找到i-1個子序列的最大值+當前的值，不做為第一個的時候那么他前面的那個數字一定是i序列的，同一個子序列，又不是作為第一個，那么前面的那個貨就一定是同一個子序列的，那么當前的值是dp[i][j-1] + num[j],在兩種決策中選擇一個最有的就行了，還有就是maxx(dp[i-1][k]+num[j])的這個地方可以開一個數組記錄下來，不能每次都跑，跑不起，再有就是這個題目沒有給m的范圍，所以開不了二維數組（目測不是很大，大的話會超時，但是肯定是先超內存在超時，所以為了保險，還是吧dp[][]壓縮成一維的）那么狀態轉移就邊成這樣了dp[j]表示的是 j這個人在當前的這個子序列中的最優值，mk[j]表示的是在上一個子序列中1--j的dp的最大值，所以就變成 dp[j] = maxx(dp[j-1] + num[j] ,mk[j-1]+num[j]);還是 max(作為i個子序列的第一個元素，不是第一個元素取一個最大值)。在解釋下代碼的核心部分。

__int64 Max
for(i = 1 ;i <= m ;i ++) //枚舉子序列
{
? ?Max = - INF;
? ?for(j = i ;j <= n ;j ++) //j = i是因為每個子序列最少1個元素
? ?{
? ? ? ?if(i == j) dp[j] = mk[j-1] + num[j];//第i個元素只能是第i個子序列的第一個
? ? ? ?else
? ? ? ?dp[j] = maxx(dp[j-1] ,mk[j-1]) + num[j];
? ? ? ?mk[j-1] = Max; //這個地方注意了，不能更新mk[j]，只能更新j-1因為更新j就會被當前的這個子序列更新的時候用到。
? ? ? ?if(Max < dp[j]) Max = dp[j];
? ?}
}

最后直接輸出Max就行了，因為里面保存的正好是第m個子序列中最大的那個。

#include<stdio.h> #include<string.h>#define N 110000 #define INF 922337203685477580 __int64 num[N] ,dp[N] ,mk[N];__int64 maxx(__int64 x ,__int64 y) {return x > y ? x : y; }int main () {int n ,m ,i ,j;while(~scanf("%d %d" ,&m ,&n)){for(i = 1 ;i <= n ;i ++)scanf("%I64d" ,&num[i]);memset(dp ,0 ,sizeof(dp));memset(mk ,0 ,sizeof(mk));__int64 Max;for(i = 1 ;i <= m ;i ++){Max = -INF;for(j = i ;j <= n ;j ++){if(i == j) dp[j] = mk[j-1] + num[j];elsedp[j] = maxx(dp[j-1] ,mk[j-1]) + num[j];mk[j-1] = Max;if(Max < dp[j]) Max = dp[j];}}printf("%I64d\n" ,Max);}return 0; }

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu1024 最大m子序列和的全部內容，希望文章能夠幫你解決所遇到的問題。

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