7.txt

C++经典算法.rar很经典的

Source

Problem Id:1038  User Id:hawk 
Memory:940K  Time:62775MS 
Language:C++  Result:Accepted

Source 
#include<stdio.h> 
#include<memory.h> 
int n,m,k,D,e[12] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147},mmax,blank[10]; 
bool b[150][10]; 
int c[4][59049],curr;//t[max],s[max],f[max],c[max]; 
/*bool canput(int i,int j,int n,int m,int p); 
void del() 
{ 
    bool temp[150][10]; 
    memset(temp,0,sizeof(temp)); 
    for(int i=0;i<n;i++) 
        for(int j=0;j<m;j++) 
        { 
            if(i+2<n&&j+1<m&&canput(i,j,3,2,0)){ 
                for(int k=0;k<3;k++) 
                    for(int q=0;q<2;q++) 
                        temp[i+k][j+q]=true; 
            } 
            if(i+1<n&&j+2<m&&canput(i,j,2,3,0)){ 
                for(int k=0;k<2;k++) 
                    for(int q=0;q<3;q++) 
                        temp[i+k][j+q]=true; 
            } 
        } 
    for(i=0;i<n;i++) 
        for(int j=0;j<m;j++) 
            if(!temp[i][j])b[i][j]=true; 
}*/ 
void read() 
{ 
    //cin>>n>>m>>k; 
    int i,j; 
    scanf("%d %d %d",&n,&m,&k); 
     
    curr=2; 
    mmax=e[m]; 
    for(i=0;i<4;i++) 
        for(j=0;j<mmax;j++) 
            c[i][j]=0; 
    for(i=0;i<n;i++)for(j=0;j<m;j++)b[i][j]=false; 
    int x,y; 
    for(i=0;i<k;i++) 
    { 
        //cin>>x>>y; 
        scanf("%d %d",&x,&y); 
        b[x-1][y-1]=true; 
    } 
    for(j=0;j<m;j++) 
        blank[j]=1-b[0][j]; 
//    del(); 
} 
int getBit(int p,int j) 
{ 
    if(j<0)return 1; 
    return (p/e[j])%3; 
} 
/* 
bool canput(int i,int j,int n,int m,int p) 
{ 
    if(i<0||j<0||b[i][j]||b[i+n-1][j+m-1]||b[i][j+m-1]||b[i+n-1][j])return false; 
    if(getBit(p,j))return false; 
    if(getBit(p,j+1))return false; 
    for(int x=i;x<i+n;x++) 
        for(int y=j;y<j+m;y++) 
            if(b[x][y])return false; 
    return true; 
}*/ 
void go() 
{ 
    int bit; 
    int oldu=0; 
    for(int i=1;i<n;i++) 
        for(int j=0;j<m;j++) 
        { 
            curr=(curr+1)%4; 
            if(!b[i][j])blank[j]++;else blank[j]=0; 
            for(int p=0;p<mmax;p++) 
            { 
                bit=getBit(p,j); 
                if(bit)c[curr][p]=c[(curr+3)%4][p-e[j]]; 
                else{ 
                    int u=0; 
                    c[curr][p]=c[(curr+3)%4][p]; 
                    if(getBit(p,j-1)==0){ 
                        if(blank[j]>2&&blank[j-1]>2&&c[(curr+2)%4][p+2*e[j]+2*e[j-1]]+1>u) 
                            u=c[(curr+2)%4][p+2*e[j]+2*e[j-1]]+1; 
                        if(getBit(p,j-2)==0&&blank[j]>1&&blank[j-1]>1&&blank[j-2]>1&&c[(curr+1)%4][p+e[j]+e[j-1]+e[j-2]]+1>u) 
                            u=c[(curr+1)%4][p+e[j]+e[j-1]+e[j-2]]+1; 
                         
                    } 
                     
                    if(u>c[curr][p])c[curr][p]=u;                     
                } 
            } 
        } 

} 
void main() 
{ 
    //cin>>D; 
    scanf("%d",&D); 
    while(D--) 
    { 
        read(); 
        go(); 
        //cout<<c[curr][0]<<endl; 
        printf("%d\n",c[curr][0]); 
    } 
}