题解：B3803 [NICA #1] 上大分

koukou · 2025-01-07 16:44:23 · 题解

最近刚学dp，来写一篇题解。

我们不妨定义 dp_i,_j 为到了第 i 场比赛，参加了 j 场时的最高分数。

若不参加这场比赛，则 dp_i,_j 为 dp_{i-1},_j。

若参加这场比赛，则 dp_i,_j 为 dp_{i-1},_{j-1}+\lfloor\frac{a_i-dp_{i-1},_{j-1}}{4}\rfloor，但是这里有 division 2，所以需判断 dp_{i-1},_{j-1} 是否小于 1900。

再讲初始化，dp_0,_0=x。

最后是答案，及在 dp_n,_0 到 dp_n,_k 之间去最大值即可。

code:

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 1;
int n, k, x, ans = -1e9, dp[N][N];
struct node
{
    int x, c;
}s[N];
int main()
{
    cin >> n >> k >> x;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i].x >> s[i].c;
    }
    dp[0][0] = x;//初始化
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= min(i, k); j++)
        {
            if(j == 0)
            {
                dp[i][j] = dp[i - 1][j];
            }
            else if(s[i].x == 1 || s[i].x == 2 && dp[i - 1][j - 1] < 1900)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (int)floor((s[i].c - dp[i - 1][j - 1]) / 4.0));
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }//状态转移
        }
    }
    for(int i = 0; i <= k; i++)
    {
        ans = max(ans, dp[n][i]);
    }//答案
    cout << ans;
    return 0;
}