G7002 [GESP202312 七级] 纸牌游戏 题解

知识点：动态规划、状态设计、滚动数组。

解题思路

DP状态记录已处理轮数、累计换牌次数t、当前手势h。可保持手势取得本轮收益，或从其他手势换来并支付第t次换牌费用，使用滚动数组。

为什么正确

任意策略按本轮是否换牌分两类，记录累计次数使费用确定，枚举旧手势覆盖所有前驱。

易错点

费用取累计第t次而非第i轮；不可达状态置负无穷，初始三种手势均可免费选择。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n),b(n),c(n);
    for(auto &x:a)cin>>x;
    for(int i=1;i<n;i++)cin>>b[i];
    for(auto &x:c)cin>>x;
    vector<array<long long,3>>dp(n),ndp(n);
    for(auto &x:dp)x.fill(-(1LL<<60));
    dp[0].fill(0);
    for(int i=0;i<n;i++) {
        for(auto &x:ndp)x.fill(-(1LL<<60));
        for(int t=0;t<=i;t++)for(int h=0;h<3;h++) {
            long long gain=a[i]*(h==c[i]?1:((h-c[i]+3)%3==1?2:0));
            ndp[t][h]=max(ndp[t][h],dp[t][h]+gain);
            if(t)for(int z=0;z<3;z++)if(z!=h)ndp[t][h]=max(ndp[t][h],dp[t-1][z]+gain-b[t]);
        }
        dp.swap(ndp);
    }
    long long ans=0;
    for(auto &x:dp)for(auto v:x)ans=max(ans,v);
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。