竞赛讨论区 > 牛客多校5 H题求解
头像
newnewbird
编辑于 2023-07-31 19:54
+ 关注

牛客多校5 H题求解

各位dalao,可以帮我看看H题为什么会WA96.15%啊,求求啦

(上面的代码是WA的,下面的代码是AC的,就把滚动优化01背包不要了就AC了,是为什么呢?)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[220], b[220], sz[100886];
long long dp[220][220], dp01[220], val[220][220][220];

void init() {
    for(int l = 1; l <= n; l++) {
        memset(dp01, 0, sizeof(dp01));
        for(int r = l; r <= n; r++) {
            for(int num = 200; num >= a[r]; num--) {
                dp01[num] = max(dp01[num], dp01[num - a[r]] + b[r]);
                val[num][l][r] = dp01[num];
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= m; i++) cin >> sz[i];
    init();

    int beg = max(m - n + 1, 1ll);
    for(int i = beg; i <= m; i++) 
        for(int r = 0; r <= n; r++) 
            for(int l = 0; l <= r; l++) 
                dp[i - beg + 1][r] = max(dp[i - beg + 1][r], dp[i - beg][l] + val[sz[i]][l + 1][r]);

    cout << dp[m - beg + 1][n] << '\n';
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[220], b[220], sz[100886];
long long dp[220][220], dp01[220], f[220][220][220];

void init()
{
    for(int l = 1; l <= n; l++) {
        for(int r = l; r <= n; r++) {
            for(int k = 1; k <= 200; k++) {
                if(k - a[r] < 0) f[l][r][k] = f[l][r - 1][k]; 
                else f[l][r][k] = max(f[l][r - 1][k], f[l][r - 1][k - a[r]] + b[r]);
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= m; i++) cin >> sz[i];
    init();

    int beg = max(m - n + 1, 1ll);
    for(int i = beg; i <= m; i++) 
        for(int r = 0; r <= n; r++) 
            for(int l = 0; l <= r; l++) 
                dp[i - beg + 1][r] = max(dp[i - beg + 1][r], dp[i - beg][l] + f[l + 1][r][sz[i]]);

    // for (int i = 1; i <= n; i++) {
    //     cout << dp[m - beg + 1][i] << ' ';
    // }
    // cout << '\n';
    cout << dp[m - beg + 1][n] << '\n';
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐