红牌

红牌

题目

【题目描述】

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括n个步骤。每一步骤都由*的某个工作人员负责检查你所提交的材料是否符合条件。

为了加快进程，每一步*都派了m个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开*”的政策，*部门把每一个工作人员的处理一个申请所花天数都对外界公开。

为了防止所有申请人都到效率高的工作人员去申请。这m×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≤i≤m)行的第j个数表示小组i完成第j步所花的天数，天数都不超过1000000。

【输出格式】

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

【数据规模】

对于100%的数据，有n≤2000,m≤2000。

解析

又是一道dp水题。

可以很容易的看出这题有3个量：小组，步骤，天数。

由于天数是所求的量，所以肯定不能拿来用。

于是可以得出f[i][j]，表示第j组第i步所需天数 。

f数组初值为极大值，边界为f[0][i]=0。

不难推出状态转移方程：

f[i][j]=f[i-1][j]+t[j][i](t[i][j]表示第i组第j步所需天数);

f[i][j]=f[i-1][j-1]+t[j][i] 。

因为m小组可以到1小组，所以在1小组这里需要特判一下。

注意不要把i和j搞混了，特别是输入的时候。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,minn=0x7f7f7f7f,t[2001][2001],f[2001][2001];//f[i][j]表示第j组第i步所需天数 
//f[i][j]=f[i-1][j]+t[j][i]或f[i-1][j-1]+t[j][i] 
int main()
{
    memset(f,0x7f7f7f7f,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) cin>>t[i][j];
        f[0][i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        f[i][1]=min(f[i][1],min(f[i-1][1]+t[1][i],f[i-1][m]+t[1][i]));//特判 
        for(int j=2;j<=m;j++) f[i][j]=min(f[i][j],min(f[i-1][j]+t[j][i],f[i-1][j-1]+t[j][i]));
    }
    for(int i=1;i<=m;i++) minn=min(minn,f[n][i]);
    cout<<minn;
    return 0;
}