?
題目描述
某地臨時居民想獲得長期居住權就必須申請拿到紅牌。獲得紅牌的過程是相當復雜 ，一共包括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天。你可以發現沒有比這樣效率更高的選擇。
你的任務是求出完成申請所花最少天數。
輸入輸出格式
輸入格式：
?
輸入文件red.in的第一行是兩個正整數N和M,表示步數和小組數。接下來有M行，每行N個非負整數，第i+1(1<=i<=M)行的第j個數表示小組i完成第j步所花的天數，天數都不超過1000000。
?
輸出格式：
?
輸入文件red.out僅包括1個正整數，為完成所有步所需最少天數。。
?
輸入輸出樣例
4 3 2 6 1 8 3 6 2 6 4 2 3 6
12
說明
【數據規模與約定】
對于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 #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 }
?
