C. Gerrymandering
思路:
动态规划
dp[i][j] 表示前i列，末尾是第j种情况下，A的最大得票。
j是第i和i+1列的分布情况，分为0，1，2三种类型：
转移的话只需要搞清楚j=0和j=1的情况即可，j=2与j=1的行是相反的。注意到转移时如果第一行选择横向的连续三格，那么第二行也必须选择横向的三格才能保证不出现漏格。
j=0: 可以转为dp[i+3][0] 、dp[i+1][1] 、dp[i+1][2]
j=1: 可以转为dp[i+2][0] 、dp[I+3][1]
j=2: 可以转为dp[i+2][0] 、dp[I+3][2]
代码:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
int dp[100005][3];
int c[100005][3];
void solve() {memset(dp,-1,sizeof(dp)); //注意初始化dp数组为负dp[0][0]=0;int n;cin>>n;for(int j=1;j<=2;j++){for(int i=1;i<=n;i++){char x;cin>>x;if(x=='A')c[i][j]=1;else c[i][j]=0;}}for(int i=0;i<=n;i++){for(int j=0;j<=2;j++){int val=dp[i][j];if(val<0)continue;if(j==0){int vl=((c[i+1][1]+c[i+2][1]+c[i+3][1])/2 + (c[i+1][2]+c[i+2][2]+c[i+3][2])/2 ) ; //vl是投A的票数dp[i+3][0]=max(val+vl,dp[i+3][0]); vl = (c[i+1][1]+c[i+1][2]+c[i+2][1])/2;dp[i+1][1]=max(val+vl,dp[i+1][1]);vl = (c[i+1][1]+c[i+1][2]+c[i+2][2])/2;dp[i+1][2]=max(val+vl,dp[i+1][2]);}if(j==1){int vl=(c[i+1][2]+c[i+2][1]+c[i+2][2])/2;dp[i+2][0]=max(val+vl,dp[i+2][0]);vl=((c[i+2][1]+c[i+3][1]+c[i+4][1])/2 + (c[i+1][2]+c[i+2][2]+c[i+3][2])/2 );dp[i+3][1]=max(val+vl,dp[i+3][1]); }if(j==2){int vl=(c[i+1][1]+c[i+2][1]+c[i+2][2])/2;dp[i+2][0]=max(val+vl,dp[i+2][0]);vl=((c[i+2][2]+c[i+3][2]+c[i+4][2])/2 + (c[i+1][1]+c[i+2][1]+c[i+3][1])/2 );dp[i+3][2]=max(val+vl,dp[i+3][2]); }}}
//
// for(int i=0;i<=n;i++){
// for(int j=0;j<3;j++){
// cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<" ";
// }
// cout<<endl;
// }cout<<dp[n][0]<<endl;}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}