題目鏈接

題目描述

在一個(gè)N行M列的棋盤上，讓你放若干個(gè)炮（可以是0個(gè)），使得沒有一個(gè)炮可以攻擊到另一個(gè)炮，請(qǐng)問有多少種放置方法。
(在中國象棋中炮的行走方式是：一個(gè)炮攻擊到另一個(gè)炮，當(dāng)且僅當(dāng)它們?cè)谕恍谢蛲涣兄?#xff0c;且它們之間恰好 有一個(gè)棋子。)

輸入輸出格式

輸入格式:

一行包含兩個(gè)整數(shù)N，M，之間由一個(gè)空格隔開。

輸出格式:

總共的方案數(shù)，由于該值可能很大，只需給出方案數(shù)模9999973的結(jié)果。

樣例

輸入樣例輸出樣例

1 3	7

思路

1. 30分做法

dfs,復(fù)雜度玄學(xué)

沒有代碼

2.50分做法

分析題目
當(dāng)滿足題意下,每行每列有且最多只有兩個(gè)炮
注意題目保證行或列小于等于8
考慮dp 按行或列轉(zhuǎn)移(假設(shè)按行轉(zhuǎn)移,即n<=8)
如果知道了考慮到當(dāng)前行時(shí),每列已經(jīng)放了的棋子個(gè)數(shù)
那么當(dāng)前行放棋子的方案就能夠確定(每行最多放兩個(gè))
那么如果會(huì)狀壓的同學(xué)應(yīng)該已經(jīng)會(huì)了 (逃
定義dp[n][4^m]表示當(dāng)考慮到第n行時(shí),之前所放的棋子狀態(tài)為2^2m時(shí)的方案數(shù)
通過兩位二進(jìn)制表示一列的狀態(tài) 00代表沒有放棋子 01代表放了一個(gè)棋子 11代表不能再放棋子
然后轉(zhuǎn)移就可以了

沒有代碼

3.滿分做法

考慮dp轉(zhuǎn)移過程

• 不選
• 選00->01
• 選01->11
• 選00,00->01,01
• 選00,01->01,11
• 選01,01->11,11

如果你發(fā)現(xiàn),轉(zhuǎn)移并不用知道每一列究竟放了幾個(gè)棋子的話...
定義dp[n][i][j]表示當(dāng)考慮到第n行時(shí),沒有放棋子的有i列,放了一個(gè)棋子的有j列

定義C(x,y)為在x中取y個(gè)的方案數(shù)
那么上面的轉(zhuǎn)移過程表示出來就是

• C(i+j,0)
• C(i,1)
• C(j,1)
• C(i,2)
• C(i,1)*C(j,1)
• C(j,2)

假設(shè)現(xiàn)在取了 00,01
那么就有 dp[n+1][i-1][j-1]=dp[n][i][j]*C(i,1)*C(j,1)

有代碼

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define rint register int #define ci const int& #define ll long long using namespace std;const int mod=9999973; ll dp[101][102][102]; int n,m; ll ans=0;int main(){cin>>n>>m;//初始化，在第0行，放了1個(gè)的列為0(即01為0)，放了0個(gè)的列為m(即00為m)的情況數(shù)有一種 dp[0][0][m]=1;for(rint i=0;i<n;i++)for(rint j=0;j<=m;j++)for(rint k=0;k<=m-j;k++)if(dp[i][j][k]){//如果狀態(tài)可到達(dá) if(k){//當(dāng)00數(shù)>=1時(shí) if(j)dp[i+1][j][k-1]+=dp[i][j][k]*k*j,dp[i+1][j][k-1]%=mod;//當(dāng)01數(shù)>=1時(shí)，選00，01放置 dp[i+1][j+1][k-1]+=dp[i][j][k]*k;dp[i+1][j+1][k-1]%=mod;//選00放置 if(k>1)dp[i+1][j+2][k-2]+=dp[i][j][k]*k*(k-1)/2,dp[i+1][j+2][k-2]%=mod;//當(dāng)00數(shù)>=2時(shí)，選00，00放置 }if(j){//當(dāng)01數(shù)>=1時(shí) dp[i+1][j-1][k]+=dp[i][j][k]*j;dp[i+1][j-1][k]%=mod;//選01放置 if(j>1)dp[i+1][j-2][k]+=dp[i][j][k]*j*(j-1)/2,dp[i+1][j-2][k]%=mod;//當(dāng)01數(shù)>=2時(shí)，選01，01放置 }dp[i+1][j][k]+=dp[i][j][k];dp[i+1][j][k]%=mod;//不放 }for(rint j=0;j<=m;j++)for(rint k=0;k<=m-j;k++)if(dp[n][j][k])(ans+=dp[n][j][k])%=mod;//統(tǒng)計(jì) cout<<ans;//dp數(shù)組用long long,中間存在乘法，極限情況下會(huì)爆int，親身試驗(yàn).... }

轉(zhuǎn)載于:https://www.cnblogs.com/ullio/p/9369323.html

總結(jié)

以上是生活随笔為你收集整理的AHOI2009 中国象棋的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。