题解 P1130 【红牌】
ShineEternal
2020-01-13 20:35:21
[link](https://blog.csdn.net/kkkksc03/article/details/103963852)
## description：
矩阵型，从左到右，上下相连的数字三角形。
## solution：
大体的思路与数字三角形相似。
但是这题矩形的长宽颠倒不太方便，读入的时候可以
```
scanf:a[j][i]
```
来巧妙的转换一下。（相当于把矩形给竖起来？）
这就导致（拿样例为例）：
```cpp
2 6 1 8
3 6 2 6
4 2 3 6
```
在转换之后变成了：
```cpp
2 3 4
6 6 2
1 2 3
8 6 6
```
这样的话，原本的从左上，左转移过来，现在就是左上和上。
- 然后就是到了第一行时要特判一下，因为是最后一行可以翻过去。
- 其他基本上就是数字三角形的思路了。
```cpp
#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;
}
```