自动搬运

查看原文

来自洛谷，原作者为

	whx1003 「放弃一切的少女与失去一切的贤者」

搬运于2025-08-24 21:21:18，当前版本为作者最后更新于2018-08-28 14:56:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

很明显是动规

$f[i][j]$ 表示第 $i$ 阶段第 $j$ 小组的最小天数

转移方程为

$$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$ 小组，所以可以稍微改变一下读入方式：

    scanf("%d", &a[j][i]);

代码：

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