日记

Mon Mar 03 2025

5 分钟

644 字

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

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

CF1974E Money Buys Happiness Link to

就是一个变样了的 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$ 表示当天总钱数。

CPP

#include<bits/extc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,x;
int h[55],c[55],dp[50005];
void solve()
{
    cin >> n >> x;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i] >> c[i];
        sum += c[i];
    }
    fill(dp + 1,dp + sum + 1,inf);
    int now = dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = sum; j >= c[i]; j--)
        {
            dp[j] = min(dp[j],dp[j - c[i]] + h[i]);
            if (dp[j] > now)
                dp[j] = inf;
        }
        now += x;
    }
    for (int i = sum; i >= 0; i--)
    {
        if (dp[i] < inf)
        {
            cout << i << '\n';
            break;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();    
    return 0;
}

CF1741E Sending a Sequence Over the Network Link to

想到把 $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}$ 。

CPP

#include<bits/extc++.h>
using namespace std;
int n;
void solve()
{
    cin >> n;
    vector<int>a(n + 5);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<vector<bool>>dp(n + 5,vector<bool>(2));
    dp[0][0] = dp[0][1] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (i - 1 >= a[i])
            dp[i][0] = dp[i][0] || dp[i - 1 - a[i]][0] || dp[i - 1 - a[i]][1];
        if (i <= n - a[i])
            dp[i + a[i]][1] = dp[i + a[i]][1] || dp[i - 1][0] || dp[i - 1][1];
    }
    cout << (dp[n][0] || dp[n][1] ? "YES\n" : "NO\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

日记

CF1974E Money Buys Happiness# Link to

CF1741E Sending a Sequence Over the Network# Link to

日记

CF1974E Money Buys Happiness Link to

CF1741E Sending a Sequence Over the Network Link to