【暴力DP】2021 icpc上海 I

谁践踏了优雅 2024-03-26 22:21 66阅读 0赞

[Problem - I - Codeforces][]

题意：

![01d23059f1114440bc2d82d7f8bf21f3.png][]

![83f6684abaf44a389613b634808e3744.png][]

思路：

考虑暴力DP即可

设 dp\[i\]\[j\]\[k\]表示 前 i 个物品，已经翻倍了 j 次，A点数 - B点数为 k 的最大价值和

然后分为这6种决策分类讨论就好了

![657a86d5a9d74ceb9c21d876e2037965.jpeg][]

注意数组里不能有负数，要加个偏移量 P

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 1e2 + 10;
    constexpr int M = 1e5 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    int n, K;
    int v[N], t[N];
    int dp[N][N][5220];
    
    void solve() {
        std::cin >> n >> K;
        for (int i = 1; i <= n; i ++) {
            std::cin >> v[i] >> t[i];
        }
    
        for (int i = 0; i <= n; i ++) {
            for (int j = 0; j <= K; j ++) {
                for (int k = -2600; k <= 2600; k ++) {
                    int tk = k + P;
                    dp[i][j][tk] = -Inf;
                }
            }
        }
    
        dp[0][0][0 + P] = 0;
    
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j <= K; j ++) {
                for (int k = -2600; k <= 2600; k ++) {
                    int tk = k + P;
                    if (j >= 1) dp[i][j][tk] = std::max(dp[i][j][tk], dp[i - 1][j - 1][tk]);
                    if (k - t[i] * 2 >= -2600 && j >= 1) dp[i][j][tk] = std::max(dp[i][j][tk], dp[i - 1][j - 1][tk - t[i] * 2] + v[i]);
                    if (k + t[i] * 2 <= 2600 && j >= 1) dp[i][j][tk] = std::max(dp[i][j][tk], dp[i - 1][j - 1][tk + t[i] * 2] + v[i]);
                    dp[i][j][tk] = std::max(dp[i][j][tk], dp[i - 1][j][tk]);
                    if (k - t[i] >= -2600) dp[i][j][tk] = std::max(dp[i][j][tk], dp[i - 1][j][tk - t[i]] + v[i]);
                    if (k + t[i] <= 2600) dp[i][j][tk] = std::max(dp[i][j][tk], dp[i - 1][j][tk + t[i]] + v[i]);
                }
            }
        }
    
        int ans = -Inf;
        for (int j = 0; j <= K; j ++) {
            ans = std::max(ans, dp[n][j][0 + P]);
        }
    
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - I - Codeforces]: https://codeforces.com/gym/103446/problem/I
[01d23059f1114440bc2d82d7f8bf21f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/3d91cbbaad254995a3b60c2bd1528514.png
[83f6684abaf44a389613b634808e3744.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/45074d3dc979486ca3829da837c7e55e.png
[657a86d5a9d74ceb9c21d876e2037965.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/8a770de1e2034030afd10d6d29222dee.png