POJ1038--Bugs Integrated

/********************************************************************************************* 压缩状态的动态规划 算法: 压缩的DP 1.按照线性模型的方法，一块一块算过来 2.用三进制的状态向量表示每块的信息 备注: 具体信息见附件,<<Bugs Integrated, Inc>> *********************************************************************************************/ #include<cstdio> #include<cmath> int sum[4][59049], roll, list[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}, //3的倍数 bit[11][59049], blank[10], a1, a2, x_size, y_size, badNum; bool bad[150][10], can1, can2; int main( void ) { int testsNum; scanf( "%d", &testsNum ); for ( int s = 0; s < 59049; s++ ) for ( int t = s, i = 0; i < 11 && t > 0; i++, t /= 3 ) //求状态的所有解压码 bit[i][s] = t%3; while ( testsNum-- ){ int i, j, x, y, s; scanf( "%d%d%d", &x_size, &y_size, &badNum ); for ( i = 0; i < x_size; i++ ) //初始化bad for ( j = 0; j < y_size; j++ ) bad[i][j] = false; for ( i = 1; i <= badNum; i++ ){ scanf( "%d%d", &x, &y ); bad[x-1][y-1] = true; } for ( i = 0; i < y_size; i++ ) //初始化向量blank blank[i] = 1-bad[0][i]; for ( i = 0; i < 4; i++ ) //初始化方块最优值 for ( s = 0; s < list[y_size]; s++ ) sum[i][s] = 0; roll = 0; //初始化滚动起点 for ( x = 1; x < x_size; x++ ){ for ( y = 0; y < y_size; y++ ){ if ( ! bad[x][y] ) blank[y]++; else blank[y] = 0; can1 = ( y>0 && blank[y]>2 && blank[y-1]>2 ); //可以横放 a1 = 2*list[y-1]+2*list[y]; //横放对状态向量的改变量 can2 = ( y>1 && blank[y]>1 && blank[y-1]>1 && blank[y-2]> 1 ); //可以竖放 a2 = list[y-2]+list[y-1]+list[y]; //竖放对状态向量的改变量 for ( s = 0; s < list[y_size]; s++ ){ if ( bit[y][s] != 0 ){ //不能放 sum[roll][s] = sum[(roll+1)%4][s-list[y]]; continue; } sum[roll][s] = sum[(roll+1)%4][s]; //不放 if ( y == 0 || bit[y-1][s] ) continue; if ( can1 && sum[roll][s] < sum[(roll+2)%4][s+a1]+1 ) //可以横放一个 sum[roll][s] = sum[(roll+2)%4][s+a1]+1; if ( y == 1 || bit[y-2][s] ) continue; if ( can2 && sum[roll][s] < sum[(roll+3)%4][s+a2]+1 ) //可以竖放一个 sum[roll][s] = sum[(roll+3)%4][s+a2]+1; } roll = (roll+4-1)%4; } } printf( "%d\n", sum[(roll+1)%4][0] ); } return 0; }