Codeforces - 189A - Cur Ribbon

Question

题目大意

给你一段 n 长度的绳子，要你剪断它，但是剪出来的段只能是 a 、 b 、 c 三种长度，问你最多可以剪多少段。

解析

简单的 dp : 当前的 dp[n] 是前面已经剪出来的最大值加上自己的。

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int a, b, c;
    static int[] dp;

    static int cal(int n){
        if(n < 0) //should be care 
            return Integer.MIN_VALUE;
        if(n == 0)
            return 0;
        if(dp[n] != -1)
            return dp[n];
        dp[n] = Math.max(cal(n-a), Math.max(cal(n-b), cal(n-c)))+1;
        return dp[n];
    }

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        a = cin.nextInt();
        b = cin.nextInt();
        c = cin.nextInt();
        dp = new int[n+1];
        Arrays.fill(dp, -1);
        System.out.println(cal(n));
    }
}

不用记忆化的写法:

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        int a = cin.nextInt();
        int b = cin.nextInt();
        int c = cin.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            int max = Integer.MIN_VALUE;
            if(i - a >= 0)
                max = Math.max(max, dp[i-a]);
            if(i - b >= 0)
                max = Math.max(max, dp[i-b]);
            if(i - c >= 0)
                max = Math.max(max, dp[i-c]);
            dp[i] = max + 1;
        }
        System.out.println(dp[n]);
    }
}

题目链接

https://codeforces.com/problemset/problem/189/A