POJ 3666（dp

题意：给出一个数列，求把它变成单调数列的最小成本，成本的定义是原始数列与结果数列每一项的差值的绝对值之和。

首先应该观察到，这个花费的计算与数列的顺序无关，如果调换结果数列的元素顺序，花费不变。

这样我们可以以数列的长度和最后一个数的大小作为递推下标，并且注意到结果数列中的数必然全部为原始数列中的数，所以可得如下dp。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
    public static final int maxv=2000+40;
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new File("/home/develop/eclipse_file/ACMproject/src/in"));
        // Scanner in=new Scanner(System.in);
        int[][] dp=new int[maxv][maxv];
        int N;
        N=in.nextInt();
        int[] a=new int[N];
        int[] b=new int[N];
        for(int i=0;i<N;i++){
            a[i]=in.nextInt();
            b[i]=a[i];
        }
        Arrays.sort(b);
        for(int i=0;i<N;i++) dp[0][i]=Math.abs(a[0]-b[i]);
        for(int i=1;i<N;i++){
            int pre=dp[i-1][0];
            for(int j=0;j<N;j++){
                pre=Math.min(pre, dp[i-1][j]);
                dp[i][j]=Math.abs(a[i]-b[j])+pre;
            }
        }
        int ans=(int)1e9;
        for(int i=0;i<N;i++){
            ans=Math.min(ans, dp[N-1][i]);
        }
        System.out.println(ans);
        in.close();
    }
}

View Code

相关推荐