题目链接
dp
确实没想到这种递推方式，一直绕在把整个网格分成k块，又要满足颜色不同，实在解不出来
dp的设置状态不是没想过，像这样的设置的确超出我的水平了
现在详细讲讲
只有两行，若两行的颜色块状态已知，我们是可以判断什么情况联通块会+1，什么情况是不变的，我们进行枚举即可
f[i][j][type]表示第i列，已经有j个联通块，type是上下颜色块的状态
这里我们设置0为BW，1为BB，2为WW，3为WB
来个例子：
第一列是B 第二列是B 那么我们的联通块数是不变的
W。 W 因为B与前一列的B属于同一个联通块，W同理
第一列是B 第二列是W 那么我们的联通块数+2
W。 B。 因为W不能属于前面任何一个联通块，联通块数+1，B同理
得到状态转移方程：
f[i][j][0]=f[i-1][j][0]+f[i-1][j-1][1]+f[i-1][j-1][2]+f[i-1][j-2][3];
f[i][j][1]=f[i-1][j][0]+f[i-1][j][1]+f[i-1][j-1][2]+f[i-1][j][3];
f[i][j][2]=f[i-1][j][0]+f[i-1][j-1][1]+f[i-1][j][2]+f[i-1][j][3];
f[i][j][3]=f[i-1][j-2][0]+f[i-1][j-1][1]+f[i-1][j-1][2]+f[i-1][j][3];
注意初始化第一列，第一列4种摆放方式都有可能
int n,k;
int dp[1010][2010][5];
const int mod=998244353;
void solve() {
cin>>n>>k;
dp[1][1][1]=1;dp[1][1][2]=1;dp[1][2][0]=1;dp[1][2][3]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][0])%mod;dp[i][j][0]=(dp[i][j][0]+dp[i-1][j-1][1])%mod;dp[i][j][0]=(dp[i][j][0]+dp[i-1][j-1][2])%mod;if(j>=2)dp[i][j][0]=(dp[i][j][0]+dp[i-1][j-2][3])%mod;
dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0])%mod;dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][1])%mod;dp[i][j][1]=(dp[i][j][1]+dp[i-1][j-1][2])%mod;dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][3])%mod;
dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][0])%mod;dp[i][j][2]=(dp[i][j][2]+dp[i-1][j-1][1])%mod;dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][2])%mod;dp[i][j][2]=(dp[i][j][2]+dp[i-1][j][3])%mod;
if(j>=2)dp[i][j][3]=(dp[i][j][3]+dp[i-1][j-2][0])%mod;dp[i][j][3]=(dp[i][j][3]+dp[i-1][j-1][1])%mod;dp[i][j][3]=(dp[i][j][3]+dp[i-1][j-1][2])%mod;dp[i][j][3]=(dp[i][j][3]+dp[i-1][j][3])%mod;
}
}
ll ans=0;
ans=(ans+dp[n][k][0])%mod;
ans=(ans+dp[n][k][1])%mod;
ans=(ans+dp[n][k][2])%mod;
ans=(ans+dp[n][k][3])%mod;
cout<<ans;
}
B.
又是一道从一开始就想错的题
因为后来才发现比如先往右上再往右下等价于往右移动两格，也就是用对角的方式走了水平或垂直的路，然后就去想把水平或竖直的路径变成对角的，认为直接走真正对角的不会最优
没想到就是先走真正的对角，然后再考虑把水平或竖直变成对角更为好做，服了
这个图中，我们可以把对角换成一个水平和一个竖直，也可以把一个水平和一个竖直换成一个对角
从原点到目的地需要的最小步数是max（a，b） （连这个都忘了我服了）
若k<max（a，b），那么就输出-1
考虑合法情况的最优解：
先走真正的对角到达b限定的高度
a和b表示终点坐标，设a为较大数
如果(a-b)%2==0,那么我们把用对角的方式走水平线（方式为必须两个水平线换两个对角）
第一次走到终点后，若剩余步数是偶数，那么用对角的方式从终点来回跳
若剩余步数是奇数，要求最后要走到目的地，那么就把前面的一个对角换成一条水平线和一条竖直线，此时对角的贡献-1，可以到达目的地
如果(a-b)%2==1，
那么必须要消耗一个步数走平路以到达目的地
第一次走到终点后，若剩余步数是偶数，那么以对角的方式在终点来回跳
若是奇数，把平路的那条改成对角，再花费一个步数从对角走到终点，对角+1
代码：
void solve() {
ll n,m,k;cin>>n>>m>>k;
if(n>m)swap(n,m);//n为较小数
ll res=max(n,m);//从原点到终点所需最小步数
if(res>k){//步数不够
cout<<-1<<endl;return ;
}
ll ans=n;//先把真正的对角走完，此时到达b限定的高度
ll x=k-res;//剩余的步数
ll y=abs(n-m);//多出来的那段路
if(y&1)ans+=y-1;//花费1个步数走平路，其余都走对角（是偶数）
else ans+=y;//是偶数，全走对角
if(x&1)ans+=x-1;//先把偶数个来回跳，剩下一个后面处理
else ans+=x;//偶数直接来回跳完
if(x&1&&y&1)ans++;//把平路花费的那一条变成对角，多出来的这一步从对角走到终点
else if(y%2==0&&x&1)ans--;//把原来的一个对角改成平路，再加上剩余的1个也走平路，等价于原来的那个对角
cout<<ans<<endl;
}