題目鏈接：http://poj.org/problem?id=3666

思路：

看了討論區(qū)說本題的數(shù)據(jù)比較弱，只需要考慮不減序列即可，比較懶，所以我也只寫了這一部分的代碼，思路都一樣，能AC就行了。

首先要想明白一點，就是將每一個elevation更新后的值一定是原來存在的，因為更新一個elevation最好是與前一個相等，要么與后一個相等，可以從貪心角度去想，這里要先明白，很重要。所以我們將原始數(shù)據(jù)存在a數(shù)組中，將a數(shù)組按升序排序后存在b中。用dp[i][j]表示a數(shù)組前i個數(shù)據(jù)中最后一個數(shù)據(jù)是b[j]的最小代價，則狀態(tài)轉(zhuǎn)移方程即為：dp[i][j]=dp[i-1][k]+abs(b[j]-a[i]) (k<=j)。因為求dp[i][j]時只會用到dp[i-1][k]，所以可以用滾動數(shù)組，使空間大大節(jié)省。詳見代碼：

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n,res=0x3f3f3f3f; 6 int a[2005],b[2005],dp[2005]; 7 8 int main(){ 9 scanf("%d",&n); 10 for(int i=1;i<=n;++i){ 11 scanf("%d",&a[i]); 12 b[i]=a[i]; 13 } 14 sort(b+1,b+n+1); 15 for(int i=1;i<=n;++i){ 16 int tmp=0x3f3f3f3f; 17 for(int j=1;j<=n;++j){ 18 tmp=min(tmp,dp[j]); 19 dp[j]=tmp+abs(b[j]-a[i]); 20 } 21 } 22 for(int i=1;i<=n;++i) 23 res=min(res,dp[i]); 24 printf("%d\n",res); 25 return 0; 26 }

?

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

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

總結(jié)

以上是生活随笔為你收集整理的poj3666（DP+离散化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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