5t.txt

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

Source

Problem Id:1038  User Id:00003031 
Memory:11640K  Time:58631MS 
Language:C++  Result:Accepted

Source 
/* 
   Bug Integrate 
   alogrithm:dynamic programming 
*/ 
#include <iostream> 
#include <math.h> 
#include <string> 
using namespace std; 

const int M=10; 
const int N=150; 
const int J=59049; 

int m,n,k; 
int po[M+1];  
int A[4][M][J]; 
int bug[N][M]; 

bool readbug() 
{ 
    memset(bug,0,sizeof(bug)); 
    int x,y; 
    cin>>k; 
    if(k<=0) return false; 
    for(int i=0;i<k;i++) 
    { 
        cin>>x>>y; 
        bug[x-1][y-1]=1; 
    } 
    return true; 
} 
int i,j,p; 
int convert[J][M]; 
void init() 
{ 
    int _p; 
    for(int _j=0;_j<J;_j++){ 
        _p=_j; 
        for(int _i=0;_i<M;_i++){ 
            convert[_j][_i]=_p%3; 
            _p/=3; 
        } 
    } 
    for(_p=0;_p<=M;_p++) 
        po[_p]=pow(3,_p); 

} 

bool solution() 
{ 
    int temp,t=0; 
    k=po[m]; 
    memset(A[0],0,sizeof(A[0])); 
    for(i=1;i<n;i++) 
        for(j=0;j<m;j++) 
            for(p=0;p<k;p++) 
            { 
                t=i%4; 
                if(convert[p][j]>0) 
                    A[t][j][p]=A[(i-(m-j)/m)%4][(j-1+m+m)%m][p-po[j]]; 
                else{ 
                    A[t][j][p]=A[(i-(m-j)/m)%4][(j-1+m+m)%m][p]; 
                    if(i>=2&&j>=1&&convert[p][j-1]==0&&bug[i][j]==0&&bug[i-1][j]==0&&bug[i-2][j]==0&&bug[i][j-1]==0&&bug[i-1][j-1]==0&&bug[i-2][j-1]==0&&(temp=A[(i-(m-j+1)/m)%4][(j-2+m+m)%m][p+2*po[j]+2*po[j-1]]+1)>A[t][j][p]) 
                        A[t][j][p]=temp; 
                    if(i>=1&&j>=2&&convert[p][j-1]==0&&convert[p][j-2]==0&&bug[i][j]==0&&bug[i-1][j]==0&&bug[i][j-1]==0&&bug[i-1][j-1]==0&&bug[i][j-2]==0&&bug[i-1][j-2]==0&&(temp=A[(i-(m-j+2)/m)%4][(j-3+m+m)%m][p+po[j]+po[j-1]+po[j-2]]+1)>A[t][j][p]) 
                        A[t][j][p]=temp; 
                } 
            } 
    cout<<A[(n-1)%4][m-1][0]<<endl; 
    return true; 
} 

int main() 
{ 
    int plates; 
    init(); 
    cin>>plates; 
    for(int i=1;i<=plates;i++) 
    { 
        cin>>n>>m; 
        readbug(); 
        solution(); 
    } 
    return 0; 
}