題目描述：
由于題目描述過于imba，這里直接給出鏈接吧
http://acm.hdu.edu.cn/showproblem.php?pid=4060
算法分析：
先不考慮n == m && w==h的情況：
對于白色部分，直接算。
對于黑色部分，長條的話，直接消去對應和行/列。剩下的小格子部分就是喜聞樂見的最小點覆蓋。
不過如果你認為這道regional的難題到此為止了的話O(w*h+n*m)，你就too young，too simple了。
考慮退化的情況，需要枚舉。但是總復雜度達到O(w^3)，ggg...
我的方法是預處理出(i,j)向上的連續1的個數和連續0的個數。
這樣枚舉的時候不是一行一行，而是一格一格了。
退化的復雜度O(w*(w+m))
#include<iostream>
#include<cstdio>
using namespace std;
const int V = 2005;
char ch[V];
const int N = 205;
int cx[N], cy[N], yM[N], G[N][N],n,m,chk[N],tmp[V][V][2];
int flag[N][N];
// match
int dfs(int u){
for(int v =0; v<=m; v++) if(G[u][v] && !chk[v]){
chk[v] = 1;
if(yM[v] == -1 || dfs(yM[v])) {
yM[v] = u;
return 1;
}
}
return 0;
}
//work
int h,w,t;
int work(int a,int b){
// cout<<"work: "<<a<<" "<<b<<endl;
for(int i=0;i<=n;i++) for(int j=0;j<=m;j++)
cx[i] = cy[j] = G[i][j] = flag[i][j] = 0;
for(int i=0;i<=m;i++) yM[i] = -1;
int ans = 0;
// visit all matrix
for(int i = 0,x = 0,y,flaga;;i++,x++) {
i += b -1;
for(int j=0;j<w;j++) {
y = j/(a+b);
flaga = j%(a+b) < b;
if(tmp[i][j][0] >= b) continue;
if(flaga) G[x][y] = 1;
else if(!cx[x]) ans += (cx[x] = 1);
}
i += a;
if(i >= h) break;
for(int j=0;j<w;j++) {
y = j/(a+b);
flaga = j%(a+b) < b;
if(flaga && !cy[y] && tmp[i][j][0] < a) ans += (cy[y] = 1);
else if(!flaga && !flag[x][y] && tmp[i][j][1] < a) ans += (flag[x][y] = 1);
}
}
// cout<<ans<<endl;
// solve
for(int i=0;i<=n;i++) if(cx[i])
for(int j=0;j<=m;j++) if(G[i][j])
G[i][j] = 0;
for(int i=0;i<=m;i++) if(cy[i])
for(int j=0;j<=n;j++) if(G[j][i])
G[j][i] = 0;
for(int i=0;i<=n;i++) {
for(int j=0;j<=m;j++) chk[j] = 0;
ans += dfs(i);
}
return ans;
}
int main(){
while(~scanf("%d%d%d%d%d",&h,&w,&n,&m,&t)) {
for(int i=0;i<h;i++){
scanf("%s",ch);
if(i == 0)
for(int j=0;j<w;j++)
tmp[i][j][0] = ch[j]=='0', tmp[i][j][1] = ch[j]=='1';
else
for(int j=0;j<w;j++)
if(ch[j] == '0') tmp[i][j][0] = tmp[i-1][j][0]+1, tmp[i][j][1] = 0;
else tmp[i][j][1] = tmp[i-1][j][1] +1, tmp[i][j][0] = 0;
}
int a,b,ans = -1;
if(n == m && h == w) {
for(a = 1; a*n < h; a++) if((h - a*n) % (n+1) == 0){
// cout<<a<<" "<<b<<endl;
b = (h - a*n) / (n + 1);
if(a < b) continue;
int v = work(a,b);
if(ans == -1 || ans > v) ans = v;
}
}
else {
if(n == m) ans = -1;
else if((h*m - w*n) % (m-n) == 0) {
b = (h*m - w*n) / (m-n);
if(b <= 0) ans = -1;
else if((h - (n+1)*b) % n == 0){
a = (h - (n+1)*b) / n;
if(a < b) ans = -1;
else ans = work(a,b);
}
else ans = -1;
}
else ans = -1;
}
printf("%d\n", ans > 0 ?ans * t: ans);
}
return 0;
}
posted on 2012-08-04 06:14
西月弦 閱讀(378)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告