题解 | #D. 游游买商品#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

D. 游游买商品

状态DP

令 dp[i][j][s], i为前i个项，j表示使用了多少钱，s为0,1表示状态

0表示 第i项不购买，或者半价购买

1表示 第i项全价购买

那状态转移为

dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1], dp[i - 1][j - cost[i] / 2][1] + happy[i]);

dp[i][j][1] = max(dp[i - 1][j - cost[i]][0], dp[i - 1][j - cost[i]][1]) + happy[i];

最后的结果为 max(dp[n - 1][j][s]), 0<=j<=x, s=0,1

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt(), x = sc.nextInt();
        int[] cost = new int[n];
        long[] happy = new long[n];
        for (int i = 0; i < n; i++) {
            cost[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            happy[i] = sc.nextLong();
        }

        // *)
        long inf = Long.MIN_VALUE / 10;
        long[][][] opt = new long[n][x + 1][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= x; j++) {
                opt[i][j][0] = opt[i][j][1] = inf;
            }
        }

        long ans = 0;
        if (cost[0] <= x) {
            opt[0][cost[0]][1] = happy[0];
        }
        opt[0][0][0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= x; j++) {
                opt[i][j][0] = Math.max(opt[i - 1][j][0], opt[i - 1][j][1]);
                if (j - cost[i] / 2 >= 0) {
                    opt[i][j][0] = Math.max(opt[i][j][0], opt[i - 1][j - cost[i] / 2][1] + happy[i]);
                }
                if (j - cost[i] >= 0) {
                    opt[i][j][1] = Math.max(opt[i - 1][j - cost[i]][0], opt[i - 1][j - cost[i]][1]) + happy[i];
                }
            }
        }
        for (int j = 0; j <= x; j++) {
            ans = Math.max(ans, opt[n - 1][j][0]);
            ans = Math.max(ans, opt[n - 1][j][1]);
        }

        System.out.println(ans);
    }

}