POJ 3666 Making the Grade(二维DP)

题目链接：http://poj.org/problem?id=3666

题目大意：
给出长度为n的整数数列,每次可以将一个数加1或者减1,最少要多少次可以将其变成单调不降或者单调不增(题目BUG，只能求单调不降).
解题思路：
有一个结论，每次将数字X改成Y时，Y一定是出现过的，所以可以用哈希减小数据范围。
因为只用求单调不降，所以设dp[i][j]表示将1~i变为不降序列，且把第i个数改为第Hash[j]的最小花费 .
可以得到状态转移方程dp[i][j]=min(dp[i-1][1~j])+abs(Hash[j]-a[i])

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N=2e3+5;

LL a[N],dp[N][N],Hash[N];//dp[i][j]表示将1~i变为不降序列，且把第i个数改为第Hash[j]的最小花费 
                         
LL Abs(LL a){
    return a>=0?a:-a;
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        Hash[i]=a[i];
    }
    sort(Hash+1,Hash+1+n);
    int cnt=unique(Hash+1,Hash+1+n)-Hash;
    
    for(int j=1;j<cnt;j++){
        dp[1][j]=Abs(Hash[j]-a[1]);
    }
    for(int i=2;i<=n;i++){
        LL tmp=1e18;
        for(int j=1;j<cnt;j++){
            tmp=min(tmp,dp[i-1][j]);
            dp[i][j]=Abs(Hash[j]-a[i]);
            dp[i][j]+=tmp;
        }
    }
    LL ans=1e18;
    for(int j=1;j<cnt;j++)
        ans=min(ans,dp[n][j]); 
    cout<<ans<<endl;
    return 0;
}

POJ 3666 Making the Grade(二维DP)

相关推荐