日记 - 伊埃斯的博客站

这不就找着缇宝的横版图了吗？

昨天晚上，祝老说我们太菜需要练基础的综合，于是今天早上就开始练了。

CF1974E Money Buys Happiness↗

就是一个变样了的 01 背包啊。但是值域之大， $O(n)$ 开不下。看到 $h_i \le 10^3$ ，想到能不能把答案塞到状态里。实际上可行。设 $dp_{i,j}$ 表示在前 $i$ 天共获得 $j$ 的幸福值的最小花费，转移就是普通的 01 背包的转移。但是每次转移完，都把花费大于 $now$ 的状态的 dp 值设为 $\inf$ ，表示非法。最后在 $dp_{n,j}$ 里找到最大的 $j$ 使得 $dp_{n,j} \le now$ ， $now$ 表示当天总钱数。

1
#include<bits/extc++.h>
2
#define int long long
3
#define inf 0x3f3f3f3f3f3f3f3f
4
using namespace std;
5
int n,x;
6
int h[55],c[55],dp[50005];
7
void solve()
8
{
9
    cin >> n >> x;
10
    int sum = 0;
11
    for (int i = 1; i <= n; i++)
12
    {
13
        cin >> h[i] >> c[i];
14
        sum += c[i];
15
    }
16
    fill(dp + 1,dp + sum + 1,inf);
17
    int now = dp[0] = 0;
18
    for (int i = 1; i <= n; i++)
19
    {
20
        for (int j = sum; j >= c[i]; j--)
21
        {
22
            dp[j] = min(dp[j],dp[j - c[i]] + h[i]);
23
            if (dp[j] > now)
24
                dp[j] = inf;
25
        }
26
        now += x;
27
    }
28
    for (int i = sum; i >= 0; i--)
29
    {
30
        if (dp[i] < inf)
31
        {
32
            cout << i << '\n';
33
            break;
34
        }
35
    }
36
}
37
signed main()
38
{
39
    ios::sync_with_stdio(0);
40
    cin.tie(0);
41
    cout.tie(0);
42
    int t;
43
    cin >> t;
44
    while (t--)
45
        solve();
46
    return 0;
47
}

CF1741E Sending a Sequence Over the Network↗

想到把 $n$ 个数分成不定段数的题，套路的设 $dp_i$ 表示当前段以 $i$ 结尾的答案。但是这道题还需要再来一维。 $dp_{i,0}$ 表示表示长度的数放在了当前区间后面是否可行， $dp_{i,1}$ 表示它放在了前面是否可行。

对于 $dp_{i,0}$ ，我们知道当前区间的长度，那么可以 $O(1)$ 找到前一个区间的尾，从它转移，有 $dp_{i,0} \leftarrow dp_{i - 1 - a_i,0} \lor dp_{i - 1 - a_i,0}$ 。
对于 $dp_{i,1}$ ，我们知道当前区间的长度，那么可以 $O(1)$ 找到当前区间的尾，转移到它。有 $dp_{i + a_i} \leftarrow dp_{i - 1,0} \lor dp_{i - 1,1}$ 。

1
#include<bits/extc++.h>
2
using namespace std;
3
int n;
4
void solve()
5
{
6
    cin >> n;
7
    vector<int>a(n + 5);
8
    for (int i = 1; i <= n; i++)
9
        cin >> a[i];
10
    vector<vector<bool>>dp(n + 5,vector<bool>(2));
11
    dp[0][0] = dp[0][1] = 1;
12
    for (int i = 1; i <= n; i++)
13
    {
14
        if (i - 1 >= a[i])
15
            dp[i][0] = dp[i][0] || dp[i - 1 - a[i]][0] || dp[i - 1 - a[i]][1];
16
        if (i <= n - a[i])
17
            dp[i + a[i]][1] = dp[i + a[i]][1] || dp[i - 1][0] || dp[i - 1][1];
18
    }
19
    cout << (dp[n][0] || dp[n][1] ? "YES\n" : "NO\n");
20
}
21
signed main()
22
{
23
    ios::sync_with_stdio(0);
24
    cin.tie(0);
25
    cout.tie(0);
26
    int t;
27
    cin >> t;
28
    while (t--)
29
        solve();
30
    return 0;
31
}

Thanks for reading!

日记

周一 3月 03 2025

616 字 · 5 分钟

life 日记