洛谷 P2051 [AHOI2009]中国象棋

心已赠人 2021-11-22 08:12 345阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

### 输入格式： ###

一行包含两个整数N，M，之间由一个空格隔开。

### 输出格式： ###

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

## 输入输出样例 ##

输入样例\#1： 复制

1 3

输出样例\#1： 复制

## 说明 ##

样例说明

除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2\*2\*2-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

# 题解 #

## 30分暴力 ##

搜索即可

## 50分状压 ##

题目说“N和M至少有一个数不超过8”故可以对“不超过8”的一个数状压

因为炮横向和纵向的走法是一样的，所以直接讲数组旋转一下就行了

## 100分普通dp ##

正解并不需要用任何技术，只需要利用炮的一个性质：**前面的炮只影响后面同一列的炮**

根据这一个性质，我们可以发现其实没有必要记录准确的状态，因为两个炮在哪一列并不重要，我们只要知道有几列有一个或两个炮即可。

故可以设计状态：

> $f\_\{i,j,k\}$存储方案数
> 
> $i$表示操作到第$i$行
> 
> $j$表示有$j$列有$1$个炮
> 
> $k$表示有$k$列有$2$个炮

初始化：

> $f\_\{0,0,0\}=1$

和状态转移：

> 在原有1个炮的一列加1个炮
> 
> 在原有1个炮的两列各加1个炮
> 
> 在原来是空的一列加1个炮
> 
> 在原来是空的两列各加1个炮
> 
> 在原来是空的一列加1个炮，并在原有1个炮的一列加1个炮

然后程序就很简单了，但需要注意边界

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long LL;
     4 const int MOD=9999973,MAXN=105;
     5 inline void add(LL &x,LL y){
     6     x=(x+y)%MOD;
     7 }
     8 int N,M;
     9 LL f[MAXN]/*line*/[MAXN]/*1*/[MAXN]/*2*/,ans;
    10 int main(){
    11     scanf("%d%d",&N,&M);
    12     
    13     f[0][0][0]=1;
    14     for(int i=1;i<=N;i++)
    15         for(int j=0;j<=M;j++)
    16             for(int k=0;j+k<=M;k++){
    17                 f[i][j][k]=f[i-1][j][k];/*do nothing*/
    18                 if(k)
    19                     add(f[i][j][k],f[i-1][j+1][k-1]*(j+1));/*add one to 1*/
    20                 if(k>1)/*add two to 1*/
    21                     add(f[i][j][k],f[i-1][j+2][k-2]*(j+2)*(j+1)/2);
    22                 if(j)/*add one to 0*/
    23                     add(f[i][j][k],f[i-1][j-1][k]*(M-j-k+1));
    24                 if(j>1)/*add two to 0*/
    25                     add(f[i][j][k],f[i-1][j-2][k]*(M-j-k+2)*(M-j-k+1)/2);
    26                 if(k&&j)/*add one to 0 and one to 1*/
    27                     add(f[i][j][k],f[i-1][j][k-1]*j*(M-j-k+1));
    28             }
    29     
    30     for(int i=0;i<=M;i++){
    31         for(int j=0;i+j<=M;j++){
    32             add(ans,f[N][i][j]);
    33         }
    34     }
    35     printf("%lld",ans);
    36     return 0;
    37 }

转载于:https://www.cnblogs.com/guoshaoyang/p/11122313.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/a428194f6a4f4705bb02368cd8c7f717.png