舞狮表演(dp)

 

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;int a[N][N];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x;cin>>x;if(x&1) a[i][j]=1; // 如果金额是奇数，a[i][j] = 1else a[i][j]=0;    // 如果金额是偶数，a[i][j] = 0}}int f[N][N];// 定义 DP 数组，f[i][j] 表示到达 (i,j) 的最小花费for(int i=0;i<=n;i++){fill(f[i], f[i] + n + 1, 1e9);// 将 f[i][0] 到 f[i][n] 初始化为 1e9，表示不可达a[0][i]=-1; // 设置第 0 行列为边界，值为 -1a[i][0]=-1;}f[1][1]=a[1][1] ? 0:n; // 若 a[1][1] = 0 (偶数)，花费 nfor(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=min(f[i][j], f[i-1][j]+(a[i][j]==0)*n); // 从上方 (i-1,j) 转移if(a[i][j]==a[i][j-1]) f[i][j]=min(f[i][j], f[i][j-1]); // 从左方 (i,j-1) 转移}}if(f[n][n]==1e9) cout<<"NO!"<<endl; // 若 f[n][n] 仍为 1e9，路径不可达else cout<<f[n][n]<<endl;;}return 0;
}

if (x & 1) a[i][j] = 1;

else a[i][j] = 0;        将金额转为奇偶状态，方便处理

• 奇数：a[i][j] = 1。偶数：a[i][j] = 0。

&：按位与运算符。

• 对两个操作数的每一位进行与运算：1 & 1 = 1，0 & 0 = 0，1 & 0 = 0。由于奇数的二进制表示最低位是 1，偶数的二进制表示最低位是 0。因此可以判断奇偶性

int f[N][N];到达（i,j）最小花费。（每次遇到偶数都要给一行1元，即n元）

f[1][1] = a[1][1] ? 0 : n;：

• 起点初始化：
  • 若 a[1][1] = 1（奇数），f[1][1] = 0。
  • 若 a[1][1] = 0（偶数），设为 n（花费为n）

DP 计算

向下转移：

• f[i][j] = min(f[i][j], f[i-1][j] + (a[i][j] == 0) * n);：
  • 从 (i-1,j) 到达 (i,j)。
  • 若 a[i][j] == 0（偶数），花费 n 。
  • 若 a[i][j] == 1（奇数），不用花费。

向右转移：

• if (a[i][j] == a[i][j-1]) f[i][j] = min(f[i][j], f[i][j-1]);：
  • 若当前格与左边格奇偶性相同，继承左边的花费。