link

红牌

题目描述

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括 $N$ 个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了 $M$ 个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。

为了防止所有申请人都到效率高的工作人员去申请。这 $M \times N$ 个工作人员被分成 $M$ 个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的，一定要相邻两个步骤之间来更换，而不能在某一步骤已经开始但还没结束的时候提出更换，并且也只能从原来的小组 $I$ 更换到小组 $I+1$，当然从小组 $M$ 可以更换到小组 $1$。对更换小组的次数没有限制。

例如：下面是 $3$ 个小组，每个小组 $4$ 个步骤工作天数：

• 小组 $1$： $2, 6 ,1 ,8$；
• 小组 $2$：$3,6, 2, 6$；
• 小组 $3$：$ 4, 2 ,3 ,6$。

例子中，可以选择小组 $1$ 来完成整个过程一共花了$2+6+1+8=17$ 天，也可以从小组 $2$ 开始第一步，然后第二步更换到小组 $3$，第三步到小组 $1$，第四步再到小组 $2$，这样一共花了 $3+2+1+6=12$ 天。你可以发现没有比这样效率更高的选择。

你的任务是求出完成申请所花最少天数。

输入格式

第一行是两个正整数 $N$ 和 $M$，表示步数和小组数。

接下来有 $M$ 行，每行有 $N$ 个非负整数，第 $i+1(1 \le i \le M)$ 行的第 $j$ 个数表示小组 $i$ 完成第 $j$ 步所花的天数，天数都不超过 $1000000$。

输出格式

一个正整数，为完成所有步所需最少天数。

样例 #1

样例输入 #1

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

样例输出 #1

12

提示

对于 $100%$ 的数据，$1\le N,M \le 2000$。

算法1

(线性DP)

1.数据的存储

样例给的：每行表示每个小组完成每个阶段的时间

4 3  : 4个阶段，3个小组

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

我要存储的：每列表示每个小组完成每个阶段的时间

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

也就是转置；

为何这么存储呢？
（这就是我一开始没想明白的点）

因为方便处理：到下一个阶段的转换关系
如，m->1 的情况

不同行（i-1，i）： 表示同一小组的不同阶段花费的时间 （ 由于一个列存放的是一组的数据）

不同列（j,j-1)： 表示不同组的上一个阶段的花费时间

for(int i = 1; i <= m; i++){
    for(intn j = 1; j <= n; j++){
        scanf("%d",&a[j][i]);    //！！！
    }
}

2.状态定义：

f[i][j] : 表示第i阶段由第j小组完成需要的最小时间

3.状态计算：

(1) 从上走过来的，即直接由本小组的上一个阶段走过来的

f[i-1][j] : 采用本小组的上一个阶段

(2) 从左上走过来的，即上一个小组的上一个阶段走过来的

f[i-1][j-1] ：采用上一个小组的上一个阶段

(3) 特判： 当 j = 1; 是由m组转到1组

f[i-1][j] : 上一个阶段是由同一组（第1组）过来的；

f[i-1][m] : 上一个阶段是是由m组过来的；

f[i][j] = min(f[i-1][j],f[i-1][m]) + a[i][j];

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;

int n,m;
//每一组的完成时间由每一列来表示 ，便于处理特数情况 
int a[N][N];
//f[i][j] : 第i阶段由小组j完成的最小时间    
int f[N][N];

int main(){
	scanf("%d%d",&n,&m);
	
	//样例给的是 M * N 的矩阵 
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			//每组的完成时间对应一列 
	        scanf("%d",&a[j][i]);    //这里需要注意 
		}
	}
	//求完成 n个阶段的最小天数 
	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]; 
			//到达i步： 1.由上一个阶段直接来，2.由左上来
			else f[i][j] = min(f[i-1][j-1],f[i-1][j]) + a[i][j];
		}
	}
	int ans = 0x3f3f3f3f;
	//每个小组完成i个阶段的最小值当中，取最小值 
	for(int i = 1; i <= m; i++){
		ans = min(ans,f[n][i]);
	} 
	printf("%d",ans); 
	return 0;
	
}