[数据结构与算法]P1130 红牌

P1130 红牌

思路：网上看到很多动态规划，但是始终觉得有点偏麻烦了，所以自己想了个简单的做法—对于每一列 j mp[i][j] += min(mp[i-1][j],mp[i-1][j-1])，也就是取 上一列中的上一行 和 上一列中的同一行 的最小值,由于上一行可能会是最后一行，所以记得%。不懂看下面的图片。（以题目案例为例）

AC代码如下:

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2010;
int mp[N][N];
int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>m>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) cin>>mp[i][j];
		
	for(int i=1;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			mp[j][i] += min(mp[j][i-1],mp[(j-1+n)%n][i-1]) ;
		}
	}
	int ans = inf;
	for(int i=0;i<n;i++)
	{
		ans = min(ans,mp[i][m-1]);
	}
	cout<<ans<<endl;
	return 0;
}