洛谷题解： P1130 红牌

题目描述

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

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

例如：下面是333个小组，每个小组444个步骤工作天数：

小组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≤i≤M)行的第j个数表示小组i完成第j步所花的天数，天数都不超过1000000。

输出格式：

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

样例：

输入：

输出：

分析：

最近在学dp，我比较愚笨。。虽然思想大概了解但是总是建不出模型来，还是要多锻炼。

这道题的意图很明确，要求在每一步做出的选择都要是正确的 (这里的正确指的是做出选择后的这个方向是所有选择中天数最小值最小的) 。那么肯定不能从前往后贪心选择，需要从后往前dp。

所以思路就是从倒数第二个元素开始，计算每一个备选项的天数最小值，然后循环到第一个元素（第一步），第一步的M组中最小的那个就是结果了。

AC代码：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

int main()
{
    int m,n;
    int ans = 0x3f3f3f3f;
    int a[2001][2001] = {0};

    cin>>n>>m;
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int j = n-2;j >= 0;j--)
    {
        for(int i = 0;i < m;i++)
        {
            a[i][j] = min(a[(i+1)%m][j+1], a[i][j+1]) + a[i][j];
        }
    }
    for(int i = 0;i < m;i++)
    {
        ans = min(ans,a[i][0]);
    }
    cout<<ans<<endl;
}