給你一串5000長度的數，要你將某些數變換一下，是的新的數列非遞減。。。 這種題目可以左偏樹來做的。。。數據范圍大點也沒關系，不過，，既然是5000，那就用一個n^2的吧 首先有個性質，就是變換後的數還是原來序列中的數，，，為為什麼？假設每個數都是一棵某一高度的樹，現在如果如果發現某個范圍內的樹的高度不滿足單調性，那麼就應該去改變某棵樹的高度，要麼增高它，要麼砍掉一點，那增高或者砍掉到哪個值呢，肯定是附近的某棵樹的高度！！畫一畫草圖就ok了 所以可以構造出這樣一個DP，dp[i][j]表示構造的序列中，前i個數，第i個數是小於等於a[j]的最小代價。 實現的時候還要用滾動數組，，，空間有限制 [cpp] #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N = 5100; const __int64 inf = (__int64)1<<62; __int64 a[N],b[N],dp[2][N]; __int64 min(__int64 a,__int64 b){ return a<b?a:b; } int main(){ int n,i,j; while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++) { scanf("%I64d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); memset(dp[0],0,sizeof(dp[0])); int cur = 0; for(i=1;i<=n;i++){ cur^=1; fill(dp[cur],dp[cur]+n+1,inf); for(j=1;j<=n;j++){ dp[cur][j]=min(dp[cur][j-1],dp[cur^1][j]+abs(a[i]-b[j])); } } __int64 ans=dp[cur][1]; for(i=2;i<=n;i++){ if(dp[cur][i]<ans) ans=dp[cur][i]; } printf("%I64d\n",ans); } }
