第 25 场 蓝桥月赛

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;
}