bzoj1801[AHOI2009]CHESS中国象棋

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：在棋盘上放一些炮使得它们不互相攻击。其实就是一行/一列最多放两个。

50分的数据中n，m至少有一个不超过8，比较直接的想法是对n/m中较小的一维做状态压缩,状态f[i][S1][S2]表示在前i行/列中,S1集合中的列/行放了1炮，S2集合中的列/行放了2炮。转移的时候，需要枚举第i行/列怎么放炮。这个时间复杂度好像炸天了….

仔细观察转移的过程,会发现S1和S2集合中的元素到底是谁其实无关紧要，我们只需要知道S1和S2的元素数目即可完成转移。所以可以把状态改成f[i][j][k]表示前i行有j列放了1炮,k列放了2炮的方案数，依然讨论第i行的方法，不过不需要逐个枚举方案。

因为闲得蛋疼把数组开成了两维，我的DP顺序比较奇怪…某个状态一定是从总炮数小于等于它的状态转移过来(等于的情况只有不放炮一种，写的时候不需要考虑，直接从之前继承下来),所以只要按照总炮数从大到小DP就行了。不过这题并没有卡内存,所以开成三维数组的话总是从i-1那一层转移过来,循环顺序怎样都没关系.

转移的时候,f[i][j][k]可以从f[i-1][j][k-1]转移过来,看起来是放一个炮的列数不变，放两个炮的列数+1，但不能理解成在一个空列上放两炮使得它变成有两炮的列,实际的过程是在一个空列放了一炮，在另一个之前有1炮的列上再放了1炮，因为在第i行每一列只能放一炮

我加了滚动数组之后864kb,404ms,bzoj上有人176kb就过了，而且跑得飞起,30ms.甚至还有0msAC的…不知道别人怎么做的，只能ym。

#include<cstdio>

const int maxn=,mod=;

int f[maxn][maxn];

int main(){

    int n,m;scanf("%d%d",&n,&m);

    f[][]=;

    int lim=*m;

    int ans=;

    for(int i=;i<=n;++i){

        for(int tot=lim;tot>=;--tot){//倒着枚举，类似于01背包的方法

            for(int k=;k*<=tot;++k){

                int j=tot-k*;

                if(j>m)continue;

　　　　　　　　　 //这一行放一炮

                if(j!=){

                    f[j][k]+=(m-(k)-(j-))*1LL*f[j-][k]%mod;

                }

                if(k!=){

                    f[j][k]+=(j+)*1LL*f[j+][k-]%mod;

                }

                //这一行放两炮

                if(j>=){

                    f[j][k]+=(m-k-(j-))*1LL*(m-k-(j-))/2LL*f[j-][k]%mod;

                }

                if(k>=){

                    f[j][k]+=(j+)*(j+)/2LL*f[j+][k-]%mod;

                }

                if(k>=){

                    f[j][k]+=(m-j-k+)*1LL*(j)*f[j][k-]%mod;

                }

                f[j][k]%=mod;

                if(i==n)ans=(ans+f[j][k])%mod;

            }

        }

    }

    printf("%d\n",ans);

    return ;

}