红牌
题目描述
某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括 个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了
个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。
为了防止所有申请人都到效率高的工作人员去申请。这 个工作人员被分成
个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的，一定要相邻两个步骤之间来更换，而不能在某一步骤已经开始但还没结束的时候提出更换，并且也只能从原来的小组
更换到小组
，当然从小组
可以更换到小组
。对更换小组的次数没有限制。
例如：下面是 个小组，每个小组
个步骤工作天数：
- 小组
：
；
- 小组
：
；
- 小组
：$ 4, 2 ,3 ,6$。
例子中，可以选择小组 来完成整个过程一共花了
天，也可以从小组
开始第一步，然后第二步更换到小组
，第三步到小组
，第四步再到小组
，这样一共花了
天。你可以发现没有比这样效率更高的选择。
你的任务是求出完成申请所花最少天数。
输入格式
第一行是两个正整数 和
，表示步数和小组数。
接下来有 行，每行有
个非负整数，第
行的第
个数表示小组
完成第
步所花的天数，天数都不超过
。
输出格式
一个正整数，为完成所有步所需最少天数。
样例 #1
样例输入 #1
4 3
2 6 1 8
3 6 2 6
4 2 3 6样例输出 #1
12提示
对于 的数据，
。
#include<bits/stdc++.h>
#define LL long long//此题必须用longlong否则只能那60分
using namespace std;
LL n,m,gay[2005][2005],dp[2005][2000],minn=1e8;//dp[i][j]表示第i个人做完第j个步骤的最小代价
int main()
{
cin>>n>>m;
for(LL i=1;i<=m;i++)
for(LL j=1;j<=n;j++)scanf("%d",&gay[i][j]);//读入，注意我没有像其他大佬的题解一样竖着读（主要还是我太弱了，不会反着处理~~）
for(LL j=1;j<=n;j++){//循环n个步骤
dp[0][j-1]=dp[m][j-1];//本题重点就在这里了！上一步的第零位，其实就是上一位的最后一位，因为最后一个小组是可以更换到1的
for(LL i=1;i<=m;i++)//循环m个人，每一个步骤都有m个人可以完成，挨个儿决策
dp[i][j]=min(dp[i-1][j-1],dp[i][j-1])+gay[i][j];//第i个人做第j步，可以由它的第j-1个步骤的第i-1个人或者第i个人转移过来
}
for(LL i=1;i<=m;i++)//打擂台求最小值，因为做完最后一步不一定要最后一个人完成，所以打擂台
minn=min(minn,dp[i][n]);//求做完n个步骤，最后一步由谁来做的最小值
cout<<minn;
return 0;
}