傳送門

題目描述

一個數(shù)的序列bi，當(dāng)b1 < b2 < … < bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2, …,aN)，我們可以得到一些上升的子序列(ai1, ai2, …, aiK)，這里1 <= i1 < i2 < … < iK <= N。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中序列和最大為18，為子序列(1, 3, 5, 9)的和.

你的任務(wù)，就是對于給定的序列，求出最大上升子序列和。注意，最長的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和為100，而最長上升子序列為(1, 2, 3)

輸入

輸入的第一行是序列的長度N (1 <= N <= 1000)。第二行給出序列中的N個整數(shù)，這些整數(shù)的取值范圍都在0到10000（可能重復(fù)）。

輸出

最大上升子序列和

解析

首先觀察數(shù)據(jù)范圍，可以用n方解決。
可以注意到，一個序列中，對后面有影響的只有最后一位，而再前面的選取并不影響之后的選取，因此可以用dp[i]表示以第i位結(jié)尾的最大序列和
考慮轉(zhuǎn)移：對與第i位來說，它可以由之前任意一個比起小的j得到，從而得出關(guān)系式：

if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);

從1到n遞推即可

代碼

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #define ull long long #define mem(a,b) memset(a,b,sizeof(a)); using namespace std; const int N=10050; const int P=131; int m,n,ans; int dp[N],a[N]; int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){dp[i]=a[i];for(int j=1;j<i;j++){if(a[j]>=a[i]) continue;dp[i]=max(dp[i],dp[j]+a[i]);}}ans=-2e9;for(int i=1;i<=n;i++){ans=max(ans,dp[i]); // printf("%d ",dp[i]);}printf("%d\n",ans); } /* 5 8 2 8 6 7 */

細(xì)節(jié)

本題看似順風(fēng)順?biāo)慕Y(jié)束了，但我卻沒有一次AC
就差在這一行：

dp[i]=a[i];

應(yīng)為可能存在j循環(huán)全都continue了，導(dǎo)致dp某一位=0的情況
而顯然，此時dp[i]應(yīng)等于a[i]

心得

本題應(yīng)該算dp的偏于入門的題
但之前對于dp方面的訓(xùn)練比較欠缺
這次完全獨(dú)立的情況下已接近題解的簡潔完成本題，還是不錯的awa
再難的dp，也離不開狀態(tài)轉(zhuǎn)移與最優(yōu)情況的抉擇罷了

24 OI fighting！！！！

總結(jié)

以上是生活随笔為你收集整理的动态规划：openjudge 2.6-3532 最大上升子序列和 解题心得的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。