【AHOI2009】中国象棋

2018-04-18 19:33:42


经过不懈的努力终于自己想出来了,感动
原题:

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!
N和M均不超过100

首先这题标的tag是DP,但是实际上应该是计数题,算是递推吧
和楼下mjl(stdcall)相反,这题我好像想了挺久的T_T
首先需要看出来问题的实质是给一个棋盘,每行每列最多放2个棋子求方案数
最开始我想的是安格处理,但是发现如果有两个棋子的话状态能储存的信息极少,统计答案非常困难
再次注意题目中的特殊性:
最重要的,因为这题要求的是计数,所以每个格子放在那里是不用管的,我们关心的就是方案数
第二个性质,因为每行每列上限2,所以如果将状态设为每一行里n个格子中,所在列上放了1个,0个的格子有多少个,就可以很方便地用数组表示出来
这个状态的设计我一开始就有了想法,但是没有注意到第一条的性质,认为最后统计答案会比较麻烦所以放弃了
再次注意,棋子怎么放是无所谓的,所有的情况都变成了方案数储存在数组里
这种状态相比状压,优势就在于丢掉了“每个棋子放在那里”这样一个无用的信息,而只关注我们需要的,对于每一种状态,它的方案数是多少
因为这样设计状态涵盖了所有情况,所以正确性是有保证的
(好像越描越黑了。。。。。。
总之明确了状态的设计之后,写出递推式就很容易了
对于每一行,可以不放棋子,放一个或到所在列有0个棋子的格子上,放一个或到所在列有1个棋子的格子上,两个所在列分别有1个棋子和0个棋子的格子各放一个
注意还要乘上能放的位置数,Talk is cheap, show you the code:
$$ f[i][j][k]=f[i-1][j][k]+(j+1)*f[i-1][j+1][k]+(k+1)*f[i-1][j-1][k+1]+(j+2)*(j+1)/2*f[i-1][j+2][k]+(k+2)*(k+1)/2*f[i-1][j-2][k+2]+(j)*(k+1)*f[i-1][j][k+1] $$ (有点长……
写出递推式之后就好办了,实现起来比较容易
没有需要注意的坑,把式子实现出来就能过了
我也1A了!(开心
代码:

//去掉了头文件
#define ll long long
const int mo=9999973;
int n,m;
//          1个 0个
ll f[110][110][110];
//f[i][j][k]=f[i-1][j][k]+(j+1)*f[i-1][j+1][k]+(k+1)*f[i-1][j-1][k+1]
//           +(j+2)*(j+1)/2*f[i-1][j+2][k]+(k+2)*(k+1)/2*f[i-1][j-2][k+2]
//           +(j)*(k+1)*f[i-1][j][k+1]
int main(){freopen("ddd.in","r",stdin);
    memset(f,0,sizeof(f));
    cin>>n>>m;  if(m>n)  swap(n,m);
    f[0][0][m]=1;
    for(int i=1;i<=n;++i)for(int j=0;j<=m;++j)for(int k=0;k<=m;++k){
        f[i][j][k]=f[i-1][j][k];
        if(j+1<=m)  f[i][j][k]=(f[i][j][k]+(j+1)*f[i-1][j+1][k])%mo;
        if(k+1<=m && j-1>=0)  f[i][j][k]=(f[i][j][k]+(k+1)*f[i-1][j-1][k+1])%mo;
        if(j+2<=m)  f[i][j][k]=(f[i][j][k]+(j+2)*(j+1)/2*f[i-1][j+2][k])%mo;
        if(k+2<=m && j-2>=0)  f[i][j][k]=(f[i][j][k]+(k+2)*(k+1)/2*f[i-1][j-2][k+2])%mo;
        if(k+1<=m)  f[i][j][k]=(f[i][j][k]+(j)*(k+1)*f[i-1][j][k+1])%mo;
    }
    ll ans=0;
    for(int i=0;i<=m;++i)for(int j=0;j<=m;++j)  ans=(ans+f[n][i][j])%mo;
    cout<<ans<<endl;
    return 0;
}