洛谷P1130 红牌 题解（简单dp，类似数字三角形）

description：

矩阵型，从左到右，上下相连的数字三角形。

solution：

大体的思路与数字三角形相似。

但是这题矩形的长宽颠倒不太方便，读入的时候可以

scanf:a[j][i]

来巧妙的转换一下。（相当于把矩形给竖起来？）

这就导致（拿样例为例）：

2 6 1 8
3 6 2 6
4 2 3 6

在转换之后变成了：

2 3 4
6 6 2
1 2 3
8 6 6

这样的话，原本的从左上，左转移过来，现在就是左上和上。

• 然后就是到了第一行时要特判一下，因为是最后一行可以翻过去。
• 其他基本上就是数字三角形的思路了。

#include<cstdio>
#include<algorithm>
using namespace std;
int a[2005][2005],f[2005][2005];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[j][i]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j==1)
			{
				f[i][j]=min(f[i-1][j],f[i-1][m])+a[i][j];
			}
			else
			f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
		}
	}
	int ans=2147483640;
	for(int i=1;i<=m;i++)
	{
		ans=min(ans,f[n][i]);
	}
	printf("%d\n",ans);
	return 0;
}