算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   由于题目描述过于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 西月弦 阅读(363) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理