5.舞狮表演【算法赛】 - 蓝桥云课
问题描述
春节期间，舞狮表演是必不可少的节目。今年，小蓝所在的村子也组织了一场盛大的舞狮表演。
村里的广场被划分成了一个 n×n 大大的网格。每个格子上都放着一个红包，里面装着不同金额的钱。
为了让表演更加精彩，村长决定设计一条特别的舞狮路线。舞狮队伍需要从左上角的格子出发，一路向下或向右移动，最终到达右下角的格子。
然而，狮子们“很挑剔，它们只会在装着奇数金额钱的格子上表演。因此，如果格子上装着偶数金额的钱，小蓝就需要在舞狮队伍开始移动前，偷偷地往里面塞钱。但为了不引起围观群众的注意，他每次塞钱，必须给一整行的格子里的红包都塞钱（每个红包塞一块钱）。
现在，小蓝想知道，他最少需要多少钱，才能让狮子们顺利地完成表演？如果无论如何也无法让狮子们完成表演，则输出 NO!。
输入格式
第一行包含一个整数 t ( 1≤t≤102 )，表示测试用例的数量。
每个测试用例的第一行包含一个正整数 n ( 1≤n≤103 )，表示广场网格的大小。
接下来的 n 行，每行包含 n 个整数 aij ( 1≤aij≤103 )，表示对应格子的红包金额。
数据保证输入的所有 n2 的总和不超过 106。
输出格式
对于每个测试用例，输出一行。如果可以完成表演，输出一个整数，表示小蓝最少需要多少钱；否则输出 NO!。
样例输入
2
2
1 1
2 2
3
1 2 3
4 5 6
7 8 9样例输出
2
NO!思路：
题目说的很明确，只能向右和向下走奇数格子，那么很容易写状态方程，因为就两个方向啊，记得防止越界加if（ i > 1 ）if( j > 1 )。
代码如下：
#include <iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int n,T;
int arr[N][N];
int dp[N][N];//到达i,j的最小花费
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> T; while(T--){cin >> n;for(int i = 1 ; i <= n; i++)//初始化 dp数组 {for(int j = 1 ; j <= n ; j++){dp[i][j] = 1e9;arr[i][j] = 0; }}for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= n ; j++){int t;cin >> t;if(t % 2 == 0)//偶数 arr[i][j] = 0;else//奇数 arr[i][j] = 1;}}if(arr[1][1])//特判起点 {dp[1][1] = 0;}else{dp[1][1] = n;//起点需要填n个红包 }for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= n ; j++){//向下移动 if(i > 1)dp[i][j] = min(dp[i][j], dp[i - 1][j] + (arr[i][j] == 0) * n);//向右移动 if(j > 1)if(arr[i][j] == arr[i][j - 1])dp[i][j] = min(dp[i][j], dp[i][j - 1]);}}if(dp[n][n] == 1e9) cout << "NO!" << '\n';else cout << dp[n][n] << '\n'; }return 0;
}
