題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1087

思路：這題很簡(jiǎn)單了，純LIS的解法，沒(méi)有一點(diǎn)變形，由于數(shù)據(jù)小，使用O(n^2)LIS解法就足夠了，另外由于長(zhǎng)度最長(zhǎng)的上升子序列不一定有最大的score，故LIS的O(nlogn)最優(yōu)算法不能使用，關(guān)于LIS可以參考我的另一篇隨筆：https://www.cnblogs.com/FrankChen831X/p/10384238.html。

AC代碼如下：

1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,res,a[1005],f[1005]; 5 6 int main(){ 7 while(scanf("%d",&n)!=EOF&&n){ 8 res=0; 9 for(int i=0;i<n;i++) 10 scanf("%d",&a[i]),f[i]=a[i]; 11 for(int i=0;i<n;i++){ 12 for(int j=0;j<i;j++) 13 if(a[j]<a[i]) 14 f[i]=max(f[i],f[j]+a[i]); 15 if(f[i]>res) res=f[i]; 16 } 17 printf("%d\n",res); 18 } 19 return 0; 20 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/FrankChen831X/p/10390302.html

總結(jié)

以上是生活随笔為你收集整理的hdoj1087 (DP--LIS)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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