程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj1801【AHOI2009】chess 中國象棋

bzoj1801【AHOI2009】chess 中國象棋

編輯:C++入門知識

bzoj1801【AHOI2009】chess 中國象棋


Description

在N行M列的棋盤上,放若干個炮可以是0個,使得沒有任何一個炮可以攻擊另一個炮。 請問有多少種放置方法,中國像棋中炮的行走方式大家應該很清楚吧.

Input

一行包含兩個整數N,M,中間用空格分開.

Output

輸出所有的方案數,由於值比較大,輸出其mod 9999973

Sample Input

1 3

Sample Output

7

HINT

除了在3個格子中都放滿炮的的情況外,其它的都可以.

100%的數據中N,M不超過100
50%的數據中,N,M至少有一個數不超過8
30%的數據中,N,M均不超過6

Source

Day2

一道思路很不錯的動態規劃題。

要滿足題意,只需每行每列棋子的個數都不超過2。

所以每一行都只有6種情況:

1.不放棋子

2.放一個棋子,放在之前沒有棋子的一列

3.放一個棋子,放在之前有一個棋子的一列

4.放兩個棋子,放在之前沒有棋子的兩列

5.放兩個棋子,放在之前有一個棋子的兩列

6.放兩個棋子,分別放在之前沒有棋子和有一個棋子的兩列

f[i][j][k]表示前i行,有j列是1個棋子,k列是2的棋子的方案數。然後枚舉轉移就可以了。

最終答案為∑(0≤i≤m)∑(0≤j≤m-i)f[n][i][j]。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define mod 9999973
using namespace std;
int n,m;
ll ans=0;
ll f[105][105][105];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();m=read();
	memset(f,0,sizeof(f));
	f[0][0][0]=1;
	F(i,1,n) F(j,0,m) F(k,0,m-j)
	{
		f[i][j][k]=f[i-1][j][k];
		if (j>=1) (f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1))%=mod;
		if (k>=1) (f[i][j][k]+=f[i-1][j+1][k-1]*(j+1))%=mod;
		if (j>=2) (f[i][j][k]+=f[i-1][j-2][k]*(m-j-k+2)*(m-j-k+1)/2)%=mod;
		if (k>=2) (f[i][j][k]+=f[i-1][j+2][k-2]*(j+2)*(j+1)/2)%=mod;
		if (j>=1&&k>=1) (f[i][j][k]+=f[i-1][j][k-1]*(m-j-k+1)*j)%=mod;
	}
	F(i,0,m) F(j,0,m-i) (ans+=f[n][i][j])%=mod;
	printf("%lld\n",ans);
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved