题目传送门：HDOJ 7329 [2023杭电多校] Touhou Red Red Blue

题意

有两个口袋（口袋容量为1，初始均为空），有若干个UFO按顺序来到你的面前，每个UFO有一个颜色（GRB），你可以选择 扔掉 它或者把它 装进口袋 中，如果口袋1空着必须装进口袋1；

如果口袋都满了，算上面前的UFO共有三个，有如下三种情况：

• 如果三个颜色均相同：可以消掉并获得一分（得分唯一途径），并任意选择一个颜色的UFO装进口袋1
• 如果三个颜色两辆均不同：可以消掉并选择任意两个颜色UFO装进口袋
• 其他情况：把第一个扔了，第二个放进口袋1，第三个放进口袋2

输入为字符串 \(str\) 仅包括 \(R,G,B\) ，\(|str| \le 10^5\) ，询问最多得分是多少

分析

扔掉或者装进口袋，很明显的背包 \(dp\) ，简单 \(dp\)

题解

\(dp_{i,j,k}\) 表示面前是第 \(i\) 个UFO，切目前背包1中装的是 \(j\)，背包2中装的是 \(k\)，按照题意模拟每种情况即可，注意可能有很多种前面的状态导致同一个后续状态，因此更新 \(dp\) 时每次要取 \(max\)

AC代码

#include<bits/stdc++.h>
#define int long long
#define cin std::cin
#define cout std::cout
#define fastio ios::sync_with_stdio(0), cin.tie(nullptr)
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
const int inf = 0x3fffffffffffffff;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int ret = 0,f = 0;char ch = getc();
    while (!isdigit (ch)){
        if (ch == '-') f = 1;
        ch = getc();
    }
    while (isdigit (ch)){
        ret = ret * 10 + ch - 48;
        ch = getc();
    }
    return f?-ret:ret;
}
string s;
int dp[N][5][5];
inline void init() {
    memset(dp, -0x3f, sizeof(dp));
}
inline void solve() {
    cin >> s;
    int len = s.length();
    dp[0][0][0] = 0;
    for(int i = 1; i <= len; ++i) {
        if(s[i - 1] == 'R') {
            dp[i][0][0] = dp[i][1][0] = dp[i - 1][0][0];
            for(int j = 1; j < 4; ++j) {
                dp[i][j][1] = max(dp[i - 1][j][0], dp[i][j][1]);
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j][0]);
                for(int k = 1; k < 4; ++k) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j][k]);
                    if(j != k && j != 1 && k != 1) {
                        for(int x = 1; x < 4; ++x) {
                            for(int y = 1; y < 4; ++y) {
                                dp[i][x][y] = max(dp[i - 1][j][k], dp[i][x][y]);
                            }
                        }
                    }
                    else if(j == 1 && k == 1) {
                        for(int x = 1; x < 4; ++x) {
                            dp[i][x][0] = max(dp[i - 1][j][k] + 1, dp[i][x][0]);
                        }
                    }
                    else {
                        dp[i][k][1] = max(dp[i - 1][j][k], dp[i][k][1]);
                    }
                }
            }
        }
        if(s[i - 1] == 'B') {
            dp[i][0][0] = dp[i][2][0] = dp[i - 1][0][0];
            for(int j = 1; j < 4; ++j) {
                dp[i][j][2] = max(dp[i - 1][j][0], dp[i][j][2]);
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j][0]);
                for(int k = 1; k < 4; ++k) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j][k]);
                    if(j != k && j != 2 && k != 2) {
                        for(int x = 1; x < 4; ++x) {
                            for(int y = 1; y < 4; ++y) {
                                dp[i][x][y] = max(dp[i - 1][j][k], dp[i][x][y]);
                            }
                        }
                    }
                    else if(j == 2 && k == 2) {
                        for(int x = 1; x < 4; ++x) {
                            dp[i][x][0] = max(dp[i - 1][j][k] + 1, dp[i][x][0]);
                        }
                    }
                    else {
                        dp[i][k][2] = max(dp[i - 1][j][k], dp[i][k][2]);
                    }
                }
            }
        }
        if(s[i - 1] == 'G') {
            dp[i][0][0] = dp[i][3][0] = dp[i - 1][0][0];
            for(int j = 1; j < 4; ++j) {
                dp[i][j][3] = max(dp[i - 1][j][0], dp[i][j][3]);
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j][0]);
                for(int k = 1; k < 4; ++k) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j][k]);
                    if(j != k && j != 3 && k != 3) {
                        for(int x = 1; x < 4; ++x) {
                            for(int y = 1; y < 4; ++y) {
                                dp[i][x][y] = max(dp[i - 1][j][k], dp[i][x][y]);
                            }
                        }
                    }
                    else if(j == 3 && k == 3) {
                        for(int x = 1; x < 4; ++x) {
                            dp[i][x][0] = max(dp[i - 1][j][k] + 1, dp[i][x][0]);
                        }
                    }
                    else {
                        dp[i][k][3] = max(dp[i - 1][j][k], dp[i][k][3]);
                    }
                }
            }
        }
    }
    int ans = -1;
    for(int i = 0; i < 4; ++i) {
        for(int j = 0; j < 4; ++j) {
            ans = max(ans, dp[len][i][j]);
        }
    }
    cout << ans << endl;
    return;
}
signed main() {
    fastio;
    int T;
    cin >> T;
    while(T --) {
        init();
        solve();
    }
    return 0;
}