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

Zheng_iii · 2024-12-17 12:05:48 · 题解

思路

看到这道题首先考虑贪心和动态规划。

贪心是不行的，因为这里有先减分再加分的数据，也就是说故意在 div1 的比赛掉分，使得下一次能够打 div2 加更多的分。

我们考虑动态规划，我们用 f[i][j] 表示在前 i 场比赛中得 j 分至少需要打几场比赛，就可以轻易推出这题的转移方程。

我们再进行滚动数组优化，就可以得到这道题的正解了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,k,x,dp[4010];
int main() {
    cin>>n>>k>>x;
    memset(dp,0x3f,sizeof(dp));
    dp[x]=0;
    while(n--){
        int t,a;
        int m = 4000;
        cin>>t>>a;
        if(t==2)m=1899;
        for(int j=a+1;j<=m;j++){
            int x=j-(j-a+3)/4;
            dp[x]=min(dp[x],dp[j]+1);
        }
        for(int j=min(m,a-1);j>=0;j--){
            int x=j+(a-j)/4;
            dp[x]=min(dp[x],dp[j]+1);
        }
    }
    for(int i=4000;i>=0;i--)if(!(dp[i]>k)){
        cout<<i;
        break;
    }
    return 0;
}