题解 P1130 【红牌】
whx1003
·
·
题解
很明显是动规
转移方程为
$$f[i][j]=\min(f[i-1][j],f[i-1][j-1])+a[i][j]$$
但是第 $1$ 个小组最小天数是由第 $m$ 个小组转移来的，所以需要多一个特判：
$$f[i][j]=min(f[i-1][j],j==1?f[i-1][m]:f[i-1][j-1])+a[i][j]$$
还有一个比较恶心的问题，我们读入时是按第 $i$ 小组第 $j$ 阶段存储的，但转移时变成了第 $i$ 阶段第 $j$ 小组，所以可以稍微改变一下读入方式：
```cpp
scanf("%d", &a[j][i]);
```
代码：
```cpp
#include<cstdio>
#include<algorithm>
const int maxn = 2005;
const int INF = 0x3f3f3f3f;
int n, m;
int a[maxn][maxn], f[maxn][maxn];
int main() {
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)
f[i][j] = std::min(f[i - 1][j], j == 1 ? f[i - 1][m] : f[i - 1][j - 1]) + a[i][j];
int ans = INF;
for(int i = 1; i <= m; ++i)
ans = std::min(ans, f[n][i]);
printf("%d", ans);
return 0;
}
```