销售手机网站的后期安排,网站开发规模和工作量的计算,WordPress更新时间,医院 网站建设 新闻题目描述 某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 #xff0c;一共包括N个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程#xff0c;每一步政府都派了M个工作人员来检查材料。不幸的是#xf… 题目描述 某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 一共包括N个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程每一步政府都派了M个工作人员来检查材料。不幸的是并不是每一个工作人员效率都很高。尽管如此为了体现“公开政府”的政策政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。 为了防止所有申请人都到效率高的工作人员去申请。这M*N个工作人员被分成M个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的一定要相邻两个步骤之间来更换而不能在某一步骤已经开始但还没结束的时候提出更换并且也只能从原来的小组I更换到小组I1,当然从小组M可以更换到小组1。对更换小组的次数没有限制。 例如下面是3个小组每个小组4个步骤工作天数 小组1 2 6 1 8 小组2 3 6 2 6 小组3 4 2 3 6 例子中可以选择小组1来完成整个过程一共花了261817天也可以从小组2开始第一步然后第二步更换到小组3第三步到小组1第四步再到小组2这样一共花了321612天。你可以发现没有比这样效率更高的选择。 你的任务是求出完成申请所花最少天数。 输入输出格式 输入格式 输入文件red.in的第一行是两个正整数N和M,表示步数和小组数。接下来有M行每行N个非负整数第i1(1iM)行的第j个数表示小组i完成第j步所花的天数天数都不超过1000000。 输出格式 输入文件red.out仅包括1个正整数为完成所有步所需最少天数。。 输入输出样例 输入样例#14 3
2 6 1 8
3 6 2 6
4 2 3 6输出样例#112 说明 【数据规模与约定】 对于100%的数据有N ≤ 2000, M ≤ 1000。 动态规划水题 枚举步骤数和小组数转移即可f[步骤数][完成最后一步的组]min(f[i-1][j],f[i-1][j-1]a[i][j] m组可以转移到1组需要特判。 因为把一个1敲成i还一直没看出来WA了一串…… 1 /*by SilverN*/2 #includealgorithm3 #includeiostream4 #includecstring5 #includecstdio6 #includecmath7 using namespace std;8 const int mxn2501;9 int read(){
10 int x0,f1;char chgetchar();
11 while(ch0 || ch9){if(ch-)f-1;chgetchar();}
12 while(ch0 ch9){xx*10ch-0;chgetchar();}
13 return x*f;
14 }
15 int n,m;
16 int mp[mxn][mxn];
17 int f[mxn][mxn];
18 int h[mxn][mxn],s[mxn][mxn];
19 int main(){
20 nread();mread();
21 int i,j;
22 for(i1;in;i){
23 for(j1;jm;j)
24 mp[i][j]read();
25 }
26 for(i1;in;i)
27 for(j1;jm;j){
28 if(!mp[i][j])h[i][j]h[i][j-1]1;
29 else h[i][j]0;
30 }
31 for(j1;jn;j)s[0][j]1;
32 for(i1;im;i)h[i][0]1;
33 for(i1;im;i)
34 for(j1;jn;j){
35 if(!mp[j][i])s[j][i]s[j-1][i]1;
36 else s[j][i]0;
37 }
38 int ans0;
39 for(i1;in;i)
40 for(j1;jm;j){
41 if(!mp[i][j])continue;
42 f[i][j]min(f[i-1][j-1],min(s[i-1][j],h[i][j-1]))1;
43 ansmax(f[i][j],ans);
44 }
45 for(i1;in;i){
46 for(jm;j;j--){
47 if(!mp[i][j])h[i][j]h[i][j1]1;
48 else h[i][j]0;
49 }
50 }
51 for(i1;im;i) h[i][m1]1;
52 memset(f,0,sizeof f);
53 for(i1;in;i)
54 for(j1;jm;j){
55 if(!mp[i][j])continue;
56 f[i][j]min(f[i-1][j1],min(s[i-1][j],h[i][j1]))1;
57 ansmax(ans,f[i][j]);
58 }
59 printf(%d\n,ans);
60 } 转载于:https://www.cnblogs.com/SilverNebula/p/6039572.html
