红牌
2019-08-16 07:46:57来源:博客园 阅读 ()
红牌
红牌
题目
【题目描述】
某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ,一共包括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; }View Code
原文链接:https://www.cnblogs.com/I-Love-You-520/p/11145824.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:一些笔记【杂】
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash