锐客网

  1. 首页 > it技术 > >

POJ3666

动态规划

题目来源：http://poj.org/problem?id=3666
题意：给定一个序列，可以对序列的任意一个数进行加减，使之序列成为一个不递增或者不递减的序列，改变数值1就花费价值1，问使之序列成为一个不递增或者不递减的序列最少需要多少价值。
思路：一开始看完题目，想对每个数进行分状态取递增或者递减，当到i时比较之前i-1的数值是多少，但是之前数值可取许多种不同的情况，i也有许多可取的数字情况，此方法不可行。但是发现依照不递增或者不递减情况，所有的数字变动都是依照之前的数字是多少由来，序列中的数字全部有联系，可知改变一个数值最好的情况就是变为1-n中数列的某一个数值。
之前的思路一定不行，不递增不递减前是都能化为一种情况，无非之后颠倒数列跑一边即可。所以我们可以先考虑不递减的情况。
dp[i][j]表示第i个数取值为j的时候让前i个数为不递减的序列的最小价值，列出转移方程：dp[i][j]=labs(a[i]-j)+min(dp[i-1][k])(0<=k<=j)（j的范围0-1e9）。而题中序列最大取值到1e9，必定超时。
【POJ3666】考虑到之前得出的数值改变情况是变为1-n中第某个的数值，用b[]数组排列出即可，用b数组去代替j。
dp[i][j]=labs(a[i]-b[j])+min(dp[i-1][k])(1<=k<=j)但还是为O(n*n*n)
做一点点小的改动加入temp每次对比即可变为O(n*n)，最后逆向跑一遍比较正向哪个更小即可。

#include #include #include #include #include #include #include #include #include #define MAX_len 50100*4 using namespace std; typedef long long ll; ll a[2010]; ll b[2010]; ll dp[2010][2010]; int main() { int n,i,j; cin>>n; for(i=1; i<=n; i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+1+n); for(i=1; i<=n; i++) { ll hh=9999999999; for(j=1; j<=n; j++) { hh=min(dp[i-1][j],hh); dp[i][j]=labs(a[i]-b[j])+hh; } } ll ans=999999999; for(i=1; i<=n; i++) ans=min(ans,dp[n][i]); for(i=1; i<=n; i++) { ll tmp=a[i]; a[i]=a[n-i+1]; a[n-i+1]=tmp; } memset(dp,0,sizeof(dp)); for(i=1; i<=n; i++) { ll hh=99999999999; for(j=1; j<=n; j++) { hh=min(dp[i-1][j],hh); dp[i][j]=labs(a[i]-b[j])+hh; } } for(i=1; i<=n; i++) ans=min(ans,dp[n][i]); printf("%lld",ans); return 0; }


    推荐阅读


    上一篇：华为eNSP安全策略配置

    下一篇：自学WEB到底能不能找到工作（8年前端工程师给你完美答案！）