http://poj.org/problem?id=3666
题意：给一个序列，可以给每一个数假减一个数，代价为他们改变的数的绝对值，那么要求用最小代价把序列变成单调非增或者单调非减的（ps本题数据似乎只要变成非减就能过）
n<=1e3
思路是dp
dp[i][j]表示前i个数以j为结尾的非减序列的最小代价，当然这个j得离散化的啦
dp[i]][j]=abs(a[i]-j)+dp[i-1][k] （k<=j ） ：即从i-1个序列的最优方案里选一个转移咯
似乎 看起来是 i j k三个循环
但是很显然k是满足k<=j的，那么也就是当要计算dp[i][j]时，必须要知道dp[i-1][1...j]的最小值，
而dp[i-1][1...j]肯定在 之前计算dp[i][1...j-1]时都访问过，那么我们记录一下他们的最小值mn即可
dp[i]][j]=abs(a[i]-j)+mn
复杂度n * j的范围
那么我们来看这个j，应该选什么呢，显然的话，j选择原序列的数就是最好的了，因为如果选了一个c[i]得到最优值，那么必然可以通过转换，使得最终序列花费不变，并全部用原序列的数。（贪心）
因此 i是1-n，j是a[1..n]的枚举
复杂度n^2
using namespace std; const int N=2005; const long long inf=(1<<60); int n; int a[N],b[N]; long long int dp[N][N]; void solve() { for(int i=1;i<=n;i++) { long long mn=dp[i-1][1]; for(int j=1;j<=n;j++) { mn=min(mn,dp[i-1][j]); dp[i][j]=Abs(a[i]-b[j])+mn; } } long long ans=dp[n][1]; for(int i=1;i<=n;i++) ans=min(ans,dp[n][i]); printf("%lld\n",ans); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",a+i); b[i]=a[i]; } sort(b+1,b+n+1); solve(); return 0; }
