【题目链接】

点击打开链接

【算法】

和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 ;
}

最新文章

  1. JavaScript高级程序设计--对象,数组(栈方法,队列方法,重排序方法,迭代方法)
  2. java并发编程(十四)同步问题的内存可见性
  3. 用CSS3和Canvas来画网格
  4. python基础教程-第三章-使用字符串
  5. Vim常用命令总结
  6. 六个创建模式之建造者模式(Builder Pattern)
  7. Linux root 密码重置与用户管理
  8. Grand Theft Auto V 图形研究(2)
  9. ansible自动化运维工具的安装与使用
  10. ListView中EditText的数据加载错乱的问题
  11. overrides final method getUnknownFields.()Lcom/google/protobuf/UnknownFieldSet 错误解决
  12. FreeBSD方式安装 MAC OSX
  13. vim中的一些高级命令的使用
  14. qt安装遇到的错误
  15. [转] DDD领域驱动设计(三) 之 理论知识收集汇总
  16. js获取数组中最大值和最小值
  17. 【玩转开源】制作Docker镜像
  18. loadrunner11浏览器兼容性的问题
  19. prime distance on a tree(点分治+fft)
  20. android图片绘制

热门文章

  1. 洛谷P1521 求逆序对 题解
  2. BZOJ4551 - [TJOI2016]树
  3. python学习之-- redis模块操作 HASH
  4. union关键字和字节大小端序的确定
  5. easyUI排序问题
  6. 关于maven多个模块的build顺序 [INFO] Reactor Build Order
  7. 蓦然回首,Java 已经 24 岁了!
  8. ldd
  9. 【Mongodb教程 第十五课 】MongoDB 限制记录
  10. 手把手教你_怎么找android应用的包名和启动activity