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

MTFlowCzq · 2023-07-12 21:15:35 · 题解

通过数低？没有题解？那我来写一篇吧（B 题库的题都这么难了？）

题目大意

题目传送门

有 n 场比赛，你准备选不超过 k 场来打，你希望打完以后比赛分最高，初始为 x。

你预知了每场比赛打完后的表现分，设打比赛之前的比赛分为 i，表现分为 j，则打完后比赛分会更新为 i+\lfloor\frac{j-i}{4}\rfloor。除此之外，每场比赛有 div1 和 div2 两种类型，div2 的比赛只有在打比赛前的比赛分小于 1900 时才能参与。

写程序求出最高比赛分。

解题思路

先说一句，尽管题目没有明确说，打比赛的顺序是不能调换的（常识好吧），并且别忘了限制了参加场数。

简单的贪心是不凑效的，因为样例已经给出了一组先减分再加分的数据。容易发现难点在于 div 类型的处理。

如果不考虑 div2 限分，那么使用动态规划即可解决问题，令 f_{i,j} 为前 i 场中打 j 场比赛的最高分，那么第 i+1 场比赛可以不打，也可以打了上分（容易发现表现分相同时，初始分越高，打完分数越高），转移方程为：

而在加入类型之后，可以强制下分来打 div2，那么是否可以再维护小于 1900 的最高分呢？思考后会发现难以转移（新的小于 1900 的最高分可能由更小的分数转移得到），这样做似乎不行。一种想法是用 ok_{i,j,p}=0/1 表示前 i 场比赛参加 j 场且分数为 p 的可行性，但这样三维的状态会超时，需要二维的。

经过思考以后，我们发现，可以反过来设计状态，将题目的限制和要求的得分颠倒（经典的 DP 优化手段），变为“要达到一定的分数，至少需要打多少比赛”。于是我们令 dp_{i,j} 为前 i 场比赛中分数恰为 j 时最少的比赛场数。这样，我们就可以用 dp_{i-1,j} 来更新 dp_{i,j+\lfloor\frac{a_i-j}{4}\rfloor} 了，转移式为：

而对 div2 的比赛，只需加上 j<1900 的限制条件即可。最后找出最大的满足 dp_{n,j}\le k 的 j，就是答案。

由于比赛分不会超过 \max(a_i,x)，状态数是 n\max(a_i,x)，时间复杂度是 O(n\max(a_i,x))。由于 n\le5000，a_i,x\le4000，可以通过本题。

代码

值得一提的是，空间可以使用滚动数组优化，但此时需要注意更新顺序（类似 0-1 背包，每场比赛只能打一次，所以先更新靠近 a_i 的部分）

#include<iostream>
#include<algorithm>
using namespace std;
int n,k,x,dp[4009],id,a;
int main() {
    cin>>n>>k>>x;
    for (int i=0;i<=4000;i++)
        dp[i]=10009; //初设为 INF，大于 n 即可
    dp[x]=0; //一场比赛都不打
    while (n--) {
        cin>>id>>a;
        int m=4000; if (id==2) m=1899; //参与比赛的比赛分限制
        for (int i=a+1;i<=m;i++) { //此处注意两个循环的遍历顺序
            int now=i-(i-a+3)/4; //计算打完后的分数
            dp[now]=min(dp[now],dp[i]+1); //试图更新
        }
        for (int i=min(m,a-1);i>=0;i--) {
            int now=i+(a-i)/4;
            dp[now]=min(dp[now],dp[i]+1);
        }
    }
    for (int i=4000;i>=0;i--)
        if (dp[i]<=k) { //找答案
            cout<<i<<endl; break;
        }
    return 0;
}

本人第一篇题解，如有问题和建议欢迎指出！