【2021年CCPC河南省赛】【DP】E. 简单游戏

题意：

题解：2021CCPC河南省赛 E:闯关游戏（简单DP）

思路：

看起来像是分组背包题，但是一旦往分组背包方向想就会寄。因为分组背包是每一组最多选一个，而这个题是必须选一个，所以还是要自己推一个 DP 公式。

定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 为前 i i i 关花费恰好是 j j j 的最大价值，那么初始 d p [ 0 ] [ 0 dp[0][0 dp[0][0 ~ m ] = 0 , − 1 , − 1 , − 1 ⋯ − 1 m]={0, -1, -1,-1 dots -1} m]=0,−1,−1,−1⋯−1 ，-1 代表是无效状态，不能推到其他的状态。转移方程就是 d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j − v ] + w ) ( 当 d p [ i − 1 ] [ j − v ] ! = − 1 时 ) dp[i][j]=max(dp[i-1][j-v]+w)(当dp[i-1][j-v]!=-1时) dp[i][j]=max(dp[i−1][j−v]+w)(当dp[i−1][j−v]!=−1时) 。

另外 d p [ i ] [ j ] dp[i][j] dp[i][j] 也可以定义成前 i i i 关花费上限是 j j j 的最大价值。

AC代码：http://acm.zzuli.edu.cn/showsource.php?id=6206359

#include
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
#define endl 'n'
#define fi first
#define se second
#define ppb pop_back
#define pb push_back
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof (x))
#define rep(i, l, r) for(LL i = l; i <= (r); ++ i)
#define per(i, r, l) for(LL i = r; i >= (l); -- i)
#define reps(i, l, r, d) for(LL i = l; i <= (r); i += d)
#define pers(i, r, l, d) for(LL i = r; i >= (l); i -= d)
 
template bool ckmax(T& a, T b) { return a < b ? (a = b, 1) : 0; }
template bool ckmin(T& a, T b) { return a > b ? (a = b, 1) : 0; }
 
const int N = 2e5 + 10, M = 1e5 + 10;
const LL p = 1e9 + 7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
 
LL n, h, dp[2][N];
 
void solve()
{
    cin >> n >> h;
    LL ans = 0;
    rep(i, 0, h) dp[0][i] = dp[1][i] = -1;
    dp[0][0] = 0;
    rep(i, 1, n){
        LL a, b, c, d; cin >> a >> b >> c >> d;
        rep(j, 0, h){
            dp[i & 1][j] = -1;
            if(j - a >= 0 && dp[i + 1 & 1][j - a] != -1) ckmax(dp[i & 1][j], dp[i + 1 & 1][j - a] + b);
            if(j - c >= 0 && dp[i + 1 & 1][j - c] != -1) ckmax(dp[i & 1][j], dp[i + 1 & 1][j - c] + d);
            ckmax(ans, dp[i & 1][j]);
        }
    }
    cout << ans << endl;
}
 
int main()
{
 
    ios;
 
    int T; cin >> T;
    while(T -- )
        solve();
 
 
    return 0;
}