【POJ 3666 Making the Grade】 DP

POJ3666
本题题意就是用最小代价将原序列变为单调不增或者单调不减序列，
由于单调不增和单调不减是对称的，我们先想一下单调不减的情况
这个题首先我们想一下比较暴力的转移方程
$dp[i][j]=abs(j-w[j])+min(dp[i-1][k])--(k<=j)$
很明显$dp[i-1][k]$这个状态就是上一状态中最小值，所以我们就可以把dp方程变为
$dp[i][j]=abs(j-w[j])+minn--minn=min(dp[i-1][k])$
我们发现题目中A[i]达到1e9，而且改变之后的序列每个值肯定等于原序列中的某个值，所以我们只要对原序列排序之后把j变为扫原序列就可以了。

POJ3666代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 2005;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n;
int a[maxn],b[maxn];
long long dp[maxn][maxn];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);for(int i=1;i<=n;i++){long long minn=dp[i-1][1];for(int j=1;j<=n;j++){minn=min(minn,dp[i-1][j]);dp[i][j]=abs(a[i]-b[j])+minn;}}long long ans=dp[n][1];for(int i=1;i<=n;i++)ans=min(ans,dp[n][i]);printf("%lld\n",ans);return 0;
}