91分的一点疑问
查看原帖
91分的一点疑问
833124
BIOS楼主2023/8/15 17:07
#include <iostream>
using namespace std;
const int N = 1e3 + 5, M = 105;
int res, big[N], n, m, K, top, w[N], h[N], hh[N], f[N], s;
bool st[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> h[i], hh[i] = h[i] * 0.8;
        if (h[i] >= K)
            big[++top] = i;
    }
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; j <= m; j++)
            f[j] = max(f[j], f[j - h[i]] + w[i]);
    for (int i = 0; i <= m; i++)
        res = max(res, f[i]);
    for (int i = 1; i <= top; i++)
    {
        st[big[i]] = true, s = m - h[big[i]];
        for (int j = 1; j <= n; j++)
            if (!st[j])
                for (int k = hh[j]; k <= s; k++)
                    f[k] = max(f[k], f[k - hh[j]] + w[j]);
        f[m] = max(f[m], f[s] + w[big[i]]), st[big[i]] = false;
    }
    for (int i = 1; i <= n; i++)
        if (h[i] >= K)
            res = max(res, f[m - h[i]] + w[i]);
    cout << res << endl;
}

我知道要更新f[m],所以我在循环里就更新过了,但是如果不在统计res最值的时候重新统计一遍就会错第二个点,为什么呢?我的f[m]不是更新过了吗

2023/8/15 17:07
加载中...