HDU-6781 Solo 题解

题目大意

一场比赛总共有n个题，A需要a[i]分钟写出这个题目，B需要b[i]分钟写出这个题目，每个题目率先通过的人得一分，如果同时通过，记A得一分。

A和B都是开始做一道题，就会直到这题做完或者对手通过这题。

做完了不一定要立马提交，可以之后再交。

A知道B的做题顺序是从1到n，求A最多得几分。

解题思路

比赛的时候看到这个题目的时候就是一脸懵。

跑到群里看了看，大佬说这个是dp。

更懵了。

这dp的状态我都没想到。。

刚开始是想，在前i分钟中，前j题的得分数的最大值。

但是这个分钟是$10^{18}$了，开不到。

而且好像也不好写。

写不出，看了眼题解。

发现是前i题中，得j分的最小时间。

这个思路好妙啊。

之前看y总的dp教学视频说，一般dp的值是问题所求的量。

但是这个题目不一样。

好像目前还没做过这样的题目。

那么这个题目的决策就是这个题目做与不做。

如果做，则就需要考虑B做到这个题目所需要的时间。

可以用前缀和数组pre来表示B做到这个题目所需要的时间。

如果做，所需要的时间为$dp[i - 1] [j - 1] + 1LL * a[i]$

如果这个值小于等于B做到这里的时间，则可以进行状态转移。

$\large dp[i][j] = min(dp[i][j], t)$

如果这个值大于B做到这里的时间，则说明在B做完之前，A是做不完这个题目的。

如果不做，则状态转移为$\large dp[i][j] = min(dp[i][j], dp[i - 1][j])$。

（dp老苦手了。。

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 2020;
int a[N], b[N];
ll dp[N][N], pre[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        memset(pre, 0, sizeof(pre));
        for (int i = 1; i <= n; i++)    cin >> a[i];
        for (int i = 1; i <= n; i++)    cin >> b[i], pre[i] = pre[i - 1] + b[i];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++)    dp[i][j] = 1e18;
        }
        int ans = 0;
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0;
            for (int j = 1; j <= i; j++) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
                ll t = dp[i - 1][j - 1] + 1LL * a[i];
                if (t <= pre[i])    dp[i][j] = min(dp[i][j], t);
                if (dp[i][j] != 1e18)    ans = max(ans, j);
            }
        }
        cout << ans << endl;
    }
}