P1130 红牌

题目描述

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

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

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

小组11 : 2, 6 ,1 ,82,6,1,8

小组22 : 3,6, 2, 63,6,2,6

小组33 : 4, 2 ,3 ,64,2,3,6

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

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

输入输出格式

输入格式：

第一行是两个正整数NN和MM,表示步数和小组数。接下来有MM行，每行NN个非负整数，第i+1(1 le i le M)i+1(1≤i≤M)行的第j个数表示小组ii完成第j步所花的天数，天数都不超过10000001000000。

输出格式：

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

输入输出样例

输入样例#1： 

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

输出样例#1：

12

说明

【数据规模与约定】

对于100\%100%的数据，有N ≤ 2000, M ≤ 2000N≤2000,M≤2000。

---

这道题和数字三角形思路是一样的，只不过倒了过来再加上一个特判

先是正向推：

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
int n,m,mini=10000000;

int xz[2001][2001],dp[2001][2001];
using namespace std;
int main()
{
    cin>>n>>m;//n  步数 m 小组数
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>xz[i][j];
        }
    } 
    for(int i=1;i<=m;i++)
    {
        dp[i][1]=xz[i][1];
    }
　　　　
    for(int j=2;j<=n;j++)//这里是先循环j，可以对照上面的输入样例看
    {
        for(int i=1;i<=m;i++)
        {
            if(i==1)
            {
                dp[i][j]=min(dp[i][j-1],dp[m][j-1])+xz[i][j];
            }
            else
                dp[i][j]=min(dp[i][j-1],dp[i-1][j-1])+xz[i][j];
        }
    }

    for(int i=1;i<=m;i++)
    {
        mini=min(mini,dp[i][n]);//从最后一行寻找最小的输出
    }
    cout<<mini;
}

反向抽烟操作来一波

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int n,m,a[2005][2005],ans=1<<30;//ans必须要定大，不然找不到最小值
int main(){
    scanf ("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    for (int j=0;j<n;j++)scanf ("%d",&a[i][j]);
    for (int j=n-2;j>=0;j--)//从倒数第2步开始，向第一步推进
    //我用的是0下标
    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]);//找答案
    printf ("%d",ans);//结束
    return 0;
}

这个题用我发的数字三角形的贪心做也可以，这里不再赘述