Making the Grade

? POJ - 3666?

這道題目有點意思。

我們定義dp[i][j]表示的含義是把包含前i個元素的子序列變成非遞減的子序列，并且最后一個元素變成j所需要耗費的最小代價

那么狀態(tài)轉(zhuǎn)移方程可以寫出來就是：

dp[i][j] = min(dp[i-1][k] + abs(num[i] - j)) 其中 0<= k <= j

這個方程很簡單對吧，但是問題來了

這樣的話，空間復(fù)雜度顯然會超，而且時間復(fù)雜度也會超

那么我們來考慮一下優(yōu)化問題

首先進行空間優(yōu)化，由于最多只有2000個元素，所以說不同高度的值最多也只能有2000個，那么我們對高度做個離散化，就很容易解決MLE的問題了。

下面的問題回到了時間上，由于時間是O(n3)的，而要在限定時間內(nèi)完成，我們可以把時間優(yōu)化到O(n2)

注意到我們在狀態(tài)轉(zhuǎn)移方程里，花了O(n)的時間去求了k不超過j時候的dp[i-1][k]的最小值。其實我們可以開一個數(shù)組MN[i][j]里面恰好就存不超過j時候的dp[i-1][k]的最小值。

在動態(tài)規(guī)劃的過程中進行維護這個數(shù)組就OK了

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <vector> using namespace std; const int MAX = 2005; const int INF = 1e9; int a[MAX]; int ss[MAX]; int dp[MAX][MAX]; int MN[MAX][MAX]; int main(){int N;scanf("%d",&N);for(int i = 0;i < N;i++){scanf("%d",&a[i]);ss[i] = a[i];}sort(ss,ss+N);int un = unique(ss,ss+N) - ss;for(int i = 0;i < N;i++){a[i] = lower_bound(ss,ss+un,a[i]) - ss;}for(int i = 0;i < un;i++){dp[0][i] = abs(ss[i] - ss[a[0]]);MN[0][i] = min((i == 0? 0 :MN[0][i-1]),dp[0][i]);}for(int i = 1;i < N;i++){dp[i][0] = dp[i-1][0] + abs(ss[0] - ss[a[i]]);MN[i][0] = dp[i][0];for(int j = 1;j < un;j++){dp[i][j] = INF;//for(int k = 0;k <= j;k++)//dp[i][j] = min(dp[i][j],dp[i-1][k] + abs(ss[a[i]] - ss[j]));dp[i][j] = min(dp[i][j],MN[i-1][j] + abs(ss[a[i]] - ss[j]));MN[i][j] = min(MN[i][j-1],dp[i][j]);}}int ans = INF;for(int i = 0;i < un;i++){ans = min(ans,dp[N-1][i]);}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的动态规划训练23 [Making the Grade POJ - 3666 ]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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