外贸机械网站建设,长春网站建设SEO优化营销,郑州第一附属医院不孕不育科,html个人主页源码Making the Grade POJ - 3666 这道题目有点意思。
我们定义dp[i][j]表示的含义是把包含前i个元素的子序列变成非递减的子序列#xff0c;并且最后一个元素变成j所需要耗费的最小代价
那么状态转移方程可以写出来就是#xff1a;
dp[i][j] min(dp[i-1][k] abs(num[i] - j… Making the Grade POJ - 3666 这道题目有点意思。
我们定义dp[i][j]表示的含义是把包含前i个元素的子序列变成非递减的子序列并且最后一个元素变成j所需要耗费的最小代价
那么状态转移方程可以写出来就是
dp[i][j] min(dp[i-1][k] abs(num[i] - j)) 其中 0 k j
这个方程很简单对吧但是问题来了
这样的话空间复杂度显然会超而且时间复杂度也会超
那么我们来考虑一下优化问题
首先进行空间优化由于最多只有2000个元素所以说不同高度的值最多也只能有2000个那么我们对高度做个离散化就很容易解决MLE的问题了。
下面的问题回到了时间上由于时间是O(n3)的而要在限定时间内完成我们可以把时间优化到O(n2)
注意到我们在状态转移方程里花了O(n)的时间去求了k不超过j时候的dp[i-1][k]的最小值。其实我们可以开一个数组MN[i][j]里面恰好就存不超过j时候的dp[i-1][k]的最小值。
在动态规划的过程中进行维护这个数组就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,ssN);int un unique(ss,ssN) - ss;for(int i 0;i N;i){a[i] lower_bound(ss,ssun,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]);}coutansendl;return 0;
}
