Codeforces Round 978 (Div. 2) C. Gerrymandering

很容易看出是dp题

问题是怎么推

首先，怎么问,怎么设,设为赢得的最大地区数

分类，细分,分的越细，越容易写转移方程

dp[i][0]表示完整的前i列,dp[i][1]表示完整的前i-1列,加上第i列的上部分,dp[i][2]表示完整的前i-1列,加上第i列的下部分

然后，我们要保证 dp[i] [j]的总格数是3的倍数，不然的话，当后面用到前面某个dp状态，如果都不能完全划分，根本就转移不了

保证格数是3的倍数，当i%3==0时，dp[i] [0]的格数是3的倍数，而dp[i] [1]和dp[i] [2]的格数不是3的倍数，也就是说dp[i] [1]和dp[i] [2]不需要去管，因为它不可能会用来转移

当i%3==2时，dp[i] [1]和dp[i] [2]的格数是3的倍数，画个图，进行转移即可

dp的初始化，首先，如果求最大，那么就先全部初始化为-2e9，反之初始化为2e9

然后再根据最开始进入循环需要的进行初始化

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
char s[3][N];
int dp[N][3];
int n;
int cal(int x1,int y1,int x2,int y2,int x3,int y3){int cnt=0;cnt+=s[x1][y1]=='A';cnt+=s[x2][y2]=='A';cnt+=s[x3][y3]=='A';if(cnt>=2) return 1;return 0;
}
void solve() {for(int i=1;i<=n;i++){for(int j=0;j<3;j++){dp[i][j]=-2e9;}}dp[0][0]=0;cin>>n;for(int i=1;i<=n;i++) cin>>s[1][i];for(int i=1;i<=n;i++) cin>>s[2][i];for(int i=2;i<=n;i++){if(i%3==0){dp[i][0]=max(dp[i][0],dp[i-1][2]+cal(1,i-1,1,i,2,i));dp[i][0]=max(dp[i][0],dp[i-1][1]+cal(1,i,2,i-1,2,i));dp[i][0]=max(dp[i][0],dp[i-3][0]+cal(1,i-2,1,i-1,1,i)+cal(2,i-2,2,i-1,2,i));}if(i%3==2){dp[i][1]=max(dp[i][1],dp[i-2][0]+cal(1,i-1,1,i,2,i-1));dp[i][2]=max(dp[i][2],dp[i-2][0]+cal(1,i-1,2,i-1,2,i));if(i>=3){dp[i][1]=max(dp[i][1],dp[i-3][1]+cal(1,i-2,1,i-1,1,i)+cal(2,i-3,2,i-2,2,i-1));dp[i][2]=max(dp[i][2],dp[i-3][2]+cal(1,i-3,1,i-2,1,i-1)+cal(2,i-2,2,i-1,2,i));}}}cout<<dp[n][0]<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}