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

阳光穿透心脏的1/2处 2022-04-22 02:16 179阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70][]

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;  
    \}  
\}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70]: /images/20220422/4cb0f212e63f45c48263705e22812b6e.png