本文主要是介绍【SSL_1382】车，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
车
Description
在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。
Input
第一行为棋盘的大小n
第二行为障碍的数量m
第三行到第m+3为m个障碍
Output
总数
Sample Input
4
2
1 1
2 2
Sample Output
14
解题思路
这是一道 状态压缩动态规划 模板题，所谓 状态压缩 ，就是用一个二进制数表示一个状态，比如 10100 就表示第一位和第三位放的情况，然后我们就可以DP啦（说的一点都不清楚… ）
下附代码：
#include<iostream>
#include<cstdio>
using namespace std;long long n,m,a[30],hh[30]={1},f[1<<20]={1};int main()
{cin>>n>>m;for(long long i=1;i<=n;i++)hh[i]=hh[i-1]*2;for(long long i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);a[x]+=hh[y-1]; }for(long long i=1;i<hh[n];i++){int c=0;for(long long t=i;t;c++,t-=t&(-t));for(long long t=i&~a[c];t;t-=t&(-t))f[i]+=f[i^(t&(-t))];}cout<<f[hh[n]-1]<<endl;return 0;
}
这篇关于【SSL_1382】车的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
