?

題目描述

某地臨時居民想獲得長期居住權(quán)就必須申請拿到紅牌。獲得紅牌的過程是相當(dāng)復(fù)雜 ，一共包括N個步驟。每一步驟都由政府的某個工作人員負(fù)責(zé)檢查你所提交的材料是否符合條件。為了加快進(jìn)程，每一步政府都派了M個工作人員來檢查材料。不幸的是，并不是每一個工作人員效率都很高。盡管如此，為了體現(xiàn)“公開政府”的政策，政府部門把每一個工作人員的處理一個申請所花天數(shù)都對外界公開。

為了防止所有申請人都到效率高的工作人員去申請。這M*N個工作人員被分成M個小組。每一組在每一步都有一個工作人員。申請人可以選擇任意一個小組也可以更換小組。但是更換小組是很嚴(yán)格的，一定要相鄰兩個步驟之間來更換，而不能在某一步驟已經(jīng)開始但還沒結(jié)束的時候提出更換，并且也只能從原來的小組I更換到小組I+1,當(dāng)然從小組M可以更換到小組1。對更換小組的次數(shù)沒有限制。

例如：下面是3個小組，每個小組4個步驟工作天數(shù)：

小組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天。你可以發(fā)現(xiàn)沒有比這樣效率更高的選擇。

你的任務(wù)是求出完成申請所花最少天數(shù)。

輸入輸出格式

輸入格式：

?

輸入文件red.in的第一行是兩個正整數(shù)N和M,表示步數(shù)和小組數(shù)。接下來有M行，每行N個非負(fù)整數(shù)，第i+1(1<=i<=M)行的第j個數(shù)表示小組i完成第j步所花的天數(shù)，天數(shù)都不超過1000000。

?

輸出格式：

?

輸入文件red.out僅包括1個正整數(shù)，為完成所有步所需最少天數(shù)。。

?

輸入輸出樣例

輸入樣例#1：
4 3 2 6 1 8 3 6 2 6 4 2 3 6 輸出樣例#1：
12

說明

【數(shù)據(jù)規(guī)模與約定】

對于100%的數(shù)據(jù)，有N ≤ 2000, M ≤ 1000。

?

動態(tài)規(guī)劃水題

枚舉步驟數(shù)和小組數(shù)，轉(zhuǎn)移即可：f[步驟數(shù)][完成最后一步的組]=min(f[i-1][j],f[i-1][j-1]+a[i][j]

m組可以轉(zhuǎn)移到1組，需要特判。

?

因?yàn)榘岩粋€1敲成i還一直沒看出來，WA了一串……

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=2501; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 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 n=read();m=read(); 21 int i,j; 22 for(i=1;i<=n;i++){ 23 for(j=1;j<=m;j++) 24 mp[i][j]=read(); 25 } 26 for(i=1;i<=n;i++) 27 for(j=1;j<=m;j++){ 28 if(!mp[i][j])h[i][j]=h[i][j-1]+1; 29 else h[i][j]=0; 30 } 31 for(j=1;j<=n;j++)s[0][j]=1; 32 for(i=1;i<=m;i++)h[i][0]=1; 33 for(i=1;i<=m;i++) 34 for(j=1;j<=n;j++){ 35 if(!mp[j][i])s[j][i]=s[j-1][i]+1; 36 else s[j][i]=0; 37 } 38 int ans=0; 39 for(i=1;i<=n;i++) 40 for(j=1;j<=m;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 ans=max(f[i][j],ans); 44 } 45 for(i=1;i<=n;i++){ 46 for(j=m;j;j--){ 47 if(!mp[i][j])h[i][j]=h[i][j+1]+1; 48 else h[i][j]=0; 49 } 50 } 51 for(i=1;i<=m;i++) h[i][m+1]=1; 52 memset(f,0,sizeof f); 53 for(i=1;i<=n;i++) 54 for(j=1;j<=m;j++){ 55 if(!mp[i][j])continue; 56 f[i][j]=min(f[i-1][j+1],min(s[i-1][j],h[i][j+1]))+1; 57 ans=max(ans,f[i][j]); 58 } 59 printf("%d\n",ans); 60 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/SilverNebula/p/6039572.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的洛谷P1130 红牌的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。