sgu223(崩溃)

xhSong posted @ 2009年9月11日 07:15 in 动态规划（DP） with tags sgu223 Little Kings , 2743 阅读

原题：

223. Little Kings
time limit per test: 2 sec.
memory limit per test: 65536 KB
input: standard
output: standard

After solving nice problems about bishops and rooks, Petya decided that he would like to learn to play chess. He started to learn the rules and found out that the most important piece in the game is the king.

The king can move to any adjacent cell (there are up to eight such cells). Thus, two kings are in the attacking position, if they are located on the adjacent cells.

Of course, the first thing Petya wants to know is the number of ways one can position k kings on a chessboard of size n × n so that no two of them are in the attacking position. Help him!

Input

The input file contains two integers n (1 ≤ n ≤ 10) and k (0 ≤ k ≤ n2).

Output

Print a line containing the total number of ways one can put the given number of kings on a chessboard of the given size so that no two of them are in attacking positions.

Sample test(s)

Input
Test #1

3 2

Test #2

4 4

Output
Test #1

Test #2

很显然，这是一道状态压缩DP题。

我的dp数组是f[11][101][1<<10]，f[i][j][k]表示当前是第i行，已经让入j个king，最后一行（第i行）的状态为k，如果k&(1<<p)等于说明第i行第p列放有一个king，否则为没放king。还有两个辅助数组，一个是b[1<<10]，b[i]的值为二进制i中有1的个数，这里可以用lowbit()优化快速求出b[1<<n]数组，这在转移方程中有用；另是t[1<<10][1<<10]，这个数组记录的是可行的转移状态，具体的说，t[i][0] 表示状态i可以转移到其他状态的数目，t[i][1]到t[i][t[i][0]]分别表示着t[i][0]种可转移的状态。总的来说这两个辅助数组时用来加速DP过程的。下面是我的代码，结合代码更容易理解：

#include <cstdio>
#include <cstring>
long long  f[11][101][1<<10];
int t[1<<10][1<<10],b[1<<10],n,m;

int lowbit(int x){
    return x&(-x);
}

void pretreatment()
{
    for(int i=0;i<(1<<n);i++){
        int tp = i;
        b[i] = 0;
        while( tp > 0){
            b[i] ++;
            tp -= lowbit(tp);
        }
    }
    for(int i=0;i<(1<<n);i++){
        t[i][0] = 0;
        if( (i<<1) & i) continue;
        for(int j=0;j<(1<<n);j++){
            if( (j<<1&j)==0  && (i&j)==0 && (i<<1&j)==0 && (j<<1 &i)==0){
                t[i][0] ++;
                t[i][t[i][0]] = j;
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        pretreatment();
        memset(f,0,sizeof(f));
        f[0][0][0] = 1;
        for(int i =0;i<n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k<(1<<n);k++)if(f[i][j][k])
                    for(int p =1 ;p <=t[k][0];p++)if(j+b[t[k][p]]<=m)
                        f[i+1][j+b[t[k][p]]][t[k][p]]+=f[i][j][k];
        long long  sum = 0;
        for(int i=0;i<(1<<n);i++){
            sum += f[n][m][i];
        }
        printf("%lld\n",sum);
    }
}

自我感觉着思路没有错，代码写得还比较漂亮，可郁闷的是 wrong answer on test 84，晕死……

开始的时候我把f[][][]数组定义成int，我还以为是int太小了，事实证明当输入是 10 10 时，输出已经是423677826986，这早就超出了int可以表示的范围，于是马上改成long long，满怀激动的心情按了submit，结果还是Wrong answer on test 84 73 ms 12471 kb，崩溃sgu上这到底是什么数据呀，这也太强大了吧！！！sgu果真是大牛、神牛们去的地方，去了练练可以成牛的人呀！！！膜拜一下做sgu的牛们！！！

现在估计是边界数据的问题，今天不早了，也挺纠结了，睡觉去吧，明天再来看看……