各位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) 回帖