POJ 3666 Making the Grade

题面 http://poj.org/problem?id=3666

线性dp+离散化

用dp[i][j]表示已经处理A[1~i]，B[i]的值为j的最小花费

转移方程：dp[i][j]=min{dp[i-1][k]}+|A[i]-j| (0<k<=j)

离散化：

数学归纳法可证，B中的每个数在A中出现，且N<=2000

故初始令B=A，对B排序，用i表示B[i]

而min{dp[i-1][k]}的值可用一个变量维护

总复杂度O(N)

#include<iostream>
#include<algorithm>
#define pb push_back
#define rint register int
#define It set<node>::iterator
#define endl '\n'
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=2e3+10;
const int inf=0x3f3f3f3f;

int n,ans=inf;
int a[maxn],b[maxn],dp[maxn][maxn];

int main(){
    cin>>n;
    for(rint i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    for(rint i=1;i<=n;++i){
        int val=dp[i-1][1];
        for(rint j=1;j<=n;++j){
            val=min(val,dp[i-1][j]);
            dp[i][j]=val+abs(a[i]-b[j]);
        }
    }
    for(rint i=1;i<=n;++i) ans=min(ans,dp[n][i]);
    cout<<ans<<endl;
    return 0;
}