Codeforces 1176F

快来打我* 2021-11-01 08:22 231阅读 0赞

# Codeforces 1176F #

--------------------

[题目][Link 1]

题意：T组物品，按顺序选一个一个选，物品首先要满足组间的相对顺序，每个物品有价值和体积，每组选择的体积不能超过3，组内的选择物品的顺序可以调整，在总的物品的顺序中，如果某一个物品它的编号是10的倍数，则这个物品的价值会翻倍。求最大价值。

做法：首先背包求出每一组，取j个物品构成体积k的最大价值，以及取j个物品构成体积k的且有一个价值翻倍的最大价值。在dp求 f\[i\]\[z\] 表示前i组取了的总物品数 mod 10 是 z 的最大价值，转移时，分跨过0，和不跨过0两种讨论即可。。。做法比较容易想到。。。然而dp边界卡死了。。。写起来各种问题。。。水平低啊。。。记一下这个题。以后注意了。。

#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define per(i,a,b) for(int i=(a);i>=(b);--i) #define pb push_back #define Pii pair<int,int> typedef long double db; typedef long long ll; template<class T> inline void ckmx(T &a, T b) { if(b > a) a = b; } const int N = 200010; const int Mod = 998244353; int n, a[N]; ll b[N]; ll A[N][4][4]; // A[i][j][k] 第 i 组选 j 个物品构成体积 k 的最大价值 ll g[N][4][4][2]; // g[i][j][k][0/1] 前 i 个物品, 选 j 个物品，构成体积 k，是否有一个物品价值翻倍的最大价值 ll MX[N][4][4]; // MX[i][j][k] 第 i 组选 j 个物品构成体积 k 且有一个元素价值翻倍的最大价值 ll f[N][10]; //f[i][z] 前 i 组一共用X个物品, z = X%10 int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll ans = 0; int T; cin >> T; rep(ti, 1, T) { cin >> n; rep(i,1,n) cin >> a[i] >> b[i]; auto cal = [&](ll A[4][4]) { rep(i,0,3)rep(j,0,3) A[i][j] = -1; A[0][0] = 0; rep(i,1,n) per(j,3,1) per(k,3,a[i]) if(A[j-1][k-a[i]] != -1) { ckmx(A[j][k], A[j-1][k-a[i]] + b[i]); } }; cal(A[ti]); auto cal2 = [&](ll A[4][4]) { rep(i,0,3)rep(j,0,3) A[i][j] = -1; rep(i,0,n) rep(j,0,3) rep(k,0,3) g[i][j][k][0] = g[i][j][k][1] = -1; g[0][0][0][1] = 0; g[0][0][0][0] = 0; rep(i,1,n) { rep(j,0,3) rep(k,0,3) { g[i][j][k][0] = g[i-1][j][k][0]; g[i][j][k][1] = g[i-1][j][k][1]; if( j>=1 && k >= a[i] ) { if(g[i-1][j-1][k-a[i]][0] != -1) ckmx(g[i][j][k][0], g[i-1][j-1][k-a[i]][0] + b[i]); if(g[i-1][j-1][k-a[i]][1] != -1) ckmx(g[i][j][k][1], g[i-1][j-1][k-a[i]][1] + b[i]); if(g[i-1][j-1][k-a[i]][0] != -1) ckmx(g[i][j][k][1], g[i-1][j-1][k-a[i]][0] + b[i] + b[i]); } } } rep(i,0,3)rep(j,0,3) A[i][j] = g[n][i][j][1]; }; cal2(MX[ti]); } function<int(int,int)> thz = [&](int st,int ed) -> int { int f = 0; rep(i,1,10) { if((st+i)%10 == 0) f = 1; if((st+i)%10 == ed) { if(f) return 1; } } return 0; }; rep(i,0,n)rep(j,0,9) f[i][j] = -1; f[0][0] = 0; rep(i,1,T) rep(z,0,9) { f[i][z] = f[i-1][z]; rep(j,1,3)rep(k,1,3) { if(f[i-1][(z-j+10)%10] == -1) continue; if(A[i][j][k] != -1 && !thz((z-j+10)%10,z)) ckmx(f[i][z], f[i-1][(z-j+10)%10] + A[i][j][k]); else if(MX[i][j][k] != -1 && thz((z-j+10)%10,z)) ckmx(f[i][z], f[i-1][(z-j+10)%10] + MX[i][j][k]); } ans = max(ans, f[i][z]); } cout << ans << endl; }

转载于:https://www.cnblogs.com/RRRR-wys/p/11008997.html

[Link 1]: https://codeforces.com/contest/1176/problem/F