【SSL_1383】车II

本文主要是介绍【SSL_1383】车II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

车II

---

Description

有一个nm的棋盘(n、m≤80,nm≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻。求合法的方案总数。

Input

n,m,k

Output

方案总数

Sample Input

3 3 2

Sample Output

24

解题思路

我们用 DFS 枚举每一种情况，然后枚举冲突，动态转移即可

#include<iostream>
#include<cstdio>
using namespace std;int n,m,k,s[10010],tot,c[10010],f[82][1<<9][21];void dfs(int ss,int p,int l)
{if(p>n){s[++tot]=ss;c[tot]=l;return;}dfs(ss,p+1,l);dfs(ss+(1<<p-1),p+2,l+1);
}int main()
{cin>>n>>m>>k;if(n>m)swap(n,m);dfs(0,1,0);for(int i=1;i<=tot;i++)f[1][s[i]][c[i]]=1;for(int i=2;i<=m;i++)for(int j=1;j<=tot;j++)for(int l=1;l<=tot;l++)if(!(s[j]&s[l]))for(int o=0;o<=k;o++)if(o>=c[j])f[i][s[j]][o]+=f[i-1][s[l]][o-c[j]];long long ans=0;for(int i=1;i<=tot;i++)ans+=f[m][s[i]][k];cout<<ans<<endl;
}

这篇关于【SSL_1383】车II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---