【SCOI 2005】 互不侵犯
2024-08-28 21:57:28
【题目链接】
【算法】
和HDU2167类似
先搜出一行内符合的状态,然后,f[i][j][k]表示第i行,第j种状态,放了k个,合法的方案,DP即可
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10
#define MAXK 85
const int MAXS = ; int i,j,x,y,tot,n,k,tmp,MASK;
long long f[MAXN][MAXS][MAXK];
long long ans; struct info
{
int x,s;
} ST[MAXS]; int calc(int s)
{
int i,ret = ;
for (i = ; i < n; i++)
{
if (s & ( << i))
ret++;
}
return ret;
} int main()
{ scanf("%d%d",&n,&k);
MASK = ( << n) - ;
for (i = ; i <= MASK; i++)
{
if (i & (i << )) continue;
tmp = calc(i);
if (tmp <= k) ST[++tot] = (info){i,tmp};
f[][tot][tmp] = ;
}
for (i = ; i <= n; i++)
{
for (j = ; j <= tot; j++)
{
for (x = ST[j].s; x <= k; x++)
{
for (y = ; y <= tot; y++)
{
if (ST[j].x & ST[y].x) continue;
if (ST[j].x & (ST[y].x << )) continue;
if (ST[j].x & (ST[y].x >> )) continue;
f[i][j][x] += f[i-][y][x - ST[j].s];
}
}
}
}
for (i = ; i <= tot; i++) ans += f[n][i][k]; printf("%lld\n",ans); return ;
}
最新文章
- JavaScript高级程序设计--对象,数组(栈方法,队列方法,重排序方法,迭代方法)
- java并发编程(十四)同步问题的内存可见性
- 用CSS3和Canvas来画网格
- python基础教程-第三章-使用字符串
- Vim常用命令总结
- 六个创建模式之建造者模式(Builder Pattern)
- Linux root 密码重置与用户管理
- Grand Theft Auto V 图形研究(2)
- ansible自动化运维工具的安装与使用
- ListView中EditText的数据加载错乱的问题
- overrides final method getUnknownFields.()Lcom/google/protobuf/UnknownFieldSet 错误解决
- FreeBSD方式安装 MAC OSX
- vim中的一些高级命令的使用
- qt安装遇到的错误
- [转] DDD领域驱动设计(三) 之 理论知识收集汇总
- js获取数组中最大值和最小值
- 【玩转开源】制作Docker镜像
- loadrunner11浏览器兼容性的问题
- prime distance on a tree(点分治+fft)
- android图片绘制