动态规划之直线k覆盖问题

import java.util.Scanner;

public class ZhiXianKFuGai {

    private static int n,m,r;
    private static int[] x,w,c;
    private static int[][] opt1,opt2;
    private static int MAX = 1000000;

    public static void main(String[] args){

        Scanner input = new Scanner(System.in);

        while (true){
            n = input.nextInt();
            m = input.nextInt();
            r = input.nextInt();

            x = new int[n+1];
            w = new int[n+1];
            c = new int[n+1];
            opt1 = new int[m+1][n+1];
            opt2 = new int[m+1][n+1];

            for(int i=1; i<=n; i++){
                x[i] = input.nextInt();
                w[i] = input.nextInt();
                c[i] = input.nextInt();
            }

            comp();

            System.out.println(solution());
        }
    }

    private static int solution(){
        int tmp = opt1[1][n];
        for(int i=2; i<=m; i++)
            if(opt1[i][n] < tmp)
                tmp = opt1[i][n];

        return tmp;
    }

    private static void comp(){
        int i,j,k,h,tmp;

        for(j=1; j<=n; j++){
            h = unc(j);
            opt2[1][j] = c[j];
            for(k=1; k<=h; k++)
                opt2[1][j] += w[k];
        }

        for(j=1; j<=n; j++){
            if(j > 1)
                opt1[1][j] = w[j] + opt1[1][j-1];
            else
                opt1[1][j] = MAX;
            h = cov(j);
            tmp = MAX;
            for(k=h; k<=j; k++)
                if(opt2[1][k] < tmp)
                    tmp = opt2[1][k];
            if(opt1[1][j] > tmp)
                opt1[1][j] = tmp;
        }

        for(i=2; i<=m; i++){
            for(j=i; j<=n; j++){
                h = unc(j);
                if(h < i-1)
                    h = i - 1;
                opt2[i][j] = MAX;
                for(k=h; k<j; k++){
                    tmp = opt1[i-1][k];
                    if(opt2[i][j] > tmp)
                        opt2[i][j] = tmp;
                }
                opt2[i][j] += c[j];
            }
            for(j=i; j<=n; j++){
                h = cov(j);
                if(h < i)
                    h = i;
                tmp = MAX;
                if(j > i)
                    opt1[i][j] = w[j] + opt1[i][j-1];
                else
                    opt1[i][j] = MAX;
                for(k=h; k<=j; k++)
                    if(opt2[i][k] < tmp)
                        tmp = opt2[i][k];
                if(opt1[i][j] > tmp)
                    opt1[i][j] = tmp;
            }
        }
    }

    private static int cov(int j){
        int i;
        for(i=j; i>0; i--)
            if(x[j]-x[i] > r)
                break;

        return i+1;
    }

    private static int unc(int j){
        int i;
        for(i=1; i<=j; i++)
            if(x[j]-x[i] <= r)
                break;

        return i-1;
    }
}