2142.cpp

寻最小支配集,用DP,复杂度是2^8 比2^150次方快多了

#include<stdio.h>
#include<string.h>
#define heap_capability 100000

class status{
public:
    int n,m;
    int un_light;
    char matrix[150];
    int light_count;
    int all; //all=light_count+(un_light+4)/5;
    void set(int nn,int mm){
        n=nn;
        m=mm;
        un_light=n*m;
        memset(matrix,0,150);
        light_count=0;
        all=(un_light+4)/5;
    }
    void put(int i,int j){
        //上
        if(i-1 >= 0 ){
            if( ( matrix[i-1] & ( 1 << j ) ) == 0 )  un_light--;
            matrix[i-1] |= (1 << j);
        }
        //下
        if(i+1 < n ){
            if( ( matrix[i+1] & ( 1 << j ) ) == 0 )  un_light--;
            matrix[i+1] |= (1 << j);
        }
        //左
        if(j-1 >= 0){
            if( ( matrix[i] & ( 1 << ( j-1 ) ) ) == 0 )  un_light--;
            matrix[i] |=  (1 << ( j-1 ));
        }
        //右
        if(j+1 < m){
            if( ( matrix[i] & ( 1 << ( j+1 ) ) ) == 0 )  un_light--;
            matrix[i] |= (1 << ( j+1 ));
        }
        //中
        if( ( matrix[i] & ( 1 << j ) ) == 0 )  un_light--;
        matrix[i] |= ( 1 << j );
        
        
        light_count++;
        all=light_count + (un_light+4)/5;
    }
    status(){
    }
    ~status(){
    }
};

class heap{ /*this is a minimum heap*/
public:
    int size;
    status *array;

    heap(){
        array=new status[heap_capability];
        size=1;
    }
    ~heap(){
        delete []array;
    }

    status pop_max(){
        //if(size==1) return -1;// return error

        status temp=array[1];
        array[1]=array[--size];
        int i=1;
        while( i <= (size-1)/2 ){
            int son_index=i*2;

            if(array[i*2+1].all<array[i*2].all) son_index++;

            if(array[i].all<array[son_index].all)break;

            status change=array[son_index];
            array[son_index]=array[i];
            array[i]=change;

            i=son_index;
        }

        return temp;
    }

    bool insert(status a){
        if (size >= heap_capability) return false;

        array[size]=a;
        int i=size;
        while(i>0){
            if(array[i].all<array[i/2].all){
                status change=array[i/2];
                array[i/2]=array[i];
                array[i]=change;
                i/=2;
            }
            else break;
        }
        size++;

        return true;
    }
};

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m),n!=0){
        status now;
        now.set(n,m);
        heap h;
        h.insert(now);
        int count;
        bool found=0;
        while(1){
            now=h.pop_max();
            //printf("%d\n",now.un_light);
            //printf("%d\n",now.all);
            //getchar();
            //for(int i=0;i<n;i++){
            //    for(int j=0;j<m;j++){
            //        printf("%d ",now.matrix[i]& (1<<j));
            //    }
            //    printf("\n");
            //}
            //printf("\n");

            for(int j=0;j<m;j++){
            
                int i=0;
                while( (now.matrix[i] & (1<<j)) && i<n)i++;
                if(i==n)continue;
                
                status temp;

                temp=now;
                temp.put(i,j);
                if(temp.un_light==0){
                    printf("ok\n");
                    count=temp.all;
                    found=1;
                    break;
                }
                h.insert(temp);
                
                if(i+1>=n)continue;
                temp=now;
                temp.put(i+1,j);
                if(temp.un_light==0){
                    printf("ok\n");
                    count=temp.all;
                    found=1;
                    break;
                }
                h.insert(temp);
            }
            
            if(found)break;
        }
        printf("::%d\n",count);
    }
}