codevs 2451 互不侵犯(状丫dp)
2024-10-15 06:45:38
/*
好神奇好神奇...表示自己要学的还很多
注意到n<=9 不是搜索就是状丫
搜索+剪枝 70分 枚举放或者不放
这里用状丫 f[i][j][k] 表示前i行 放了j个国王 i行的状态是k的方案数
转移的话 枚举下层的状态 算出这个状态中有几个国王 然后更新
复杂度 2^n*2^n*n*K*n 最后一个n是算国王数 这个可以预处理搞出来
还有一个问题就是 互相伤害的问题
首先在同一行里 相邻的不行 不同行的就左移右移一下就好了 顺带处理好两个状态能不能互相转移
最后Σf[n][K][i]
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 520
using namespace std;
int n,K,v1[maxn],v2[maxn][maxn],cnt[maxn];
long long ans,f[][][maxn];
void Get_v()
{
for(int i=;i<(<<n);i++)
if((i&(i>>))==)
{
v1[i]=;int c=;
for(int j=i;j;j>>=)c+=j&;
cnt[i]=c;
}
for(int i=;i<(<<n);i++)if(v1[i])
for(int j=;j<(<<n);j++)if(v1[j])
if((i&j)==&&(i&(j>>))==&&(j&(i>>))==)
v2[i][j]=;
}
int main()
{
cin>>n>>K;
Get_v();
for(int i=;i<(<<n);i++)
f[][cnt[i]][i]=;
for(int i=;i<=n;i++)
for(int j=;j<(<<n);j++)if(v1[j])
for(int k=;k<(<<n);k++)if(v2[j][k])
for(int r=cnt[j];r+cnt[k]<=K;r++)
f[i][r+cnt[k]][k]+=f[i-][r][j];
for(int i=;i<(<<n);i++)
ans+=f[n][K][i];
cout<<ans<<endl;
return ;
}
最新文章
- Logstash实践: 分布式系统的日志监控
- CentOS6.5恢复误删除的文件
- C++提前delete
- 重载new和delete
- iOS设计模式之策略模式
- 【python cookbook】【字符串与文本】2.在字符串的开头或结尾处做文本匹配
- 如何让Form窗体接收KeyDown事件?
- git常用命令2
- r.js build.js配置
- 团队作业八—第二次团队冲刺(Beta版本) 第 2 天
- 转-JavaWeb三大组件之Listener监听器
- 如何安装miniconda(python虚拟环境)
- 如何解决python 图表中文显示乱码问题(matlplotlib 包)
- 匿名内部类中使用的外部局部变量为什么只能是final变量
- Java Web开发和Python Web开发之间的区别
- Django的学习(三)————models
- centos7 sentry部署指南
- 禁用ngen版本的.NET Framework dll加载
- day6面向对象--继承、多态
- poj 2623 Sequence Median 堆的灵活运用