题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4529
题意:中文,不解释
题解:状压DP,dp[i][j][k][s]表示第i行当前用了j个骑士,i-1行的压缩状态为k,i行的压缩状态为j,然后用滚动数组优化了一下,注意如果不预处理不可存放位置会超时
#include<cstdio>
#include<cstring>
#define N (1<<8)
#define FFC(i,a,b) for(int i=a;i<=b;++i) int T,n,dp[][][N][N],g[N],num[N],f1[N][N],f2[N][N],cur,ans; void init(){//预处理不可放的位置,和每一个压缩状态的骑士数目
FFC(i,,N-){
FFC(j,,)if(i&(<<j))num[i]++;
FFC(j,,N-){
if(((i>>)&j)||((j>>)&i))f1[i][j]=;
if(((i>>)&j)||((j>>)&i))f2[i][j]=;
}
}
}
int fuck(){
memset(dp,,sizeof(dp));
cur=,ans=,dp[][][][]=;
FFC(i,,){
FFC(j,,n)FFC(p,,N-)FFC(q,,N-){
if (dp[cur][j][p][q]==)continue;
FFC(z,,N-)
if (((z&g[i+])!=z)||num[z]+j>n||(i>=&&f1[q][z])||(i>=&&f2[p][z]))continue;
else dp[cur^][num[z]+j][q][z]+=dp[cur][j][p][q];
}
memset(dp[cur],,sizeof(dp[cur])),cur^=;
}
FFC(i,,N-)FFC(j,,N-)ans+=dp[cur][n][i][j];
return ans;
} int main() {
init();char str[N];
scanf("%d",&T);
while (T--){
scanf("%d",&n);
memset(g,,sizeof(g));
FFC(i,,){
scanf("%s",str);
FFC(j,,){
g[i]<<=;
if(str[j]=='.')g[i]|=;
}
}
printf("%d\n",fuck());
}
return ;
}
hdu_4529_郑厂长系列故事——N骑士问题(状压DP)的更多相关文章
-
HDU 4529 郑厂长系列故事——N骑士问题 状压dp
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4529 郑厂长系列故事--N骑士问题 Time Limit: 6000/3000 MS (Java/O ...
-
HDU4529 郑厂长系列故事——N骑士问题 —— 状压DP
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4529 郑厂长系列故事——N骑士问题 Time Limit: 6000/3000 MS (Java/Ot ...
-
HDU 4539 郑厂长系列故事——排兵布阵 状压dp
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4539 郑厂长系列故事--排兵布阵 Time Limit: 10000/5000 MS (Java/O ...
-
HDU 4539 郑厂长系列故事——排兵布阵 —— 状压DP
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4539 郑厂长系列故事——排兵布阵 Time Limit: 10000/5000 MS (Java/Ot ...
-
hdu_4539_郑厂长系列故事——排兵布阵(状压DP|最大团)
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4539 题意:中文,不解释 题解:将每一行的状态压缩,然后进行DP,也可以用最大团做.这里我用的DP # ...
-
HDU-4529 郑厂长系列故事——N骑士问题 状态压缩DP
题意:给定一个合法的八皇后棋盘,现在给定1-10个骑士,问这些骑士不能够相互攻击的拜访方式有多少种. 分析:一开始想着搜索写,发现该题和八皇后不同,八皇后每一行只能够摆放一个棋子,因此搜索收敛的很快, ...
-
HDU----(4519)郑厂长系列故事——体检
郑厂长系列故事——体检 Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total S ...
-
HDU 4539郑厂长系列故事――排兵布阵(状压DP)
HDU 4539 郑厂长系列故事――排兵布阵 基础的状压DP,首先记录先每一行可取的所哟状态(一行里互不冲突的大概160个状态), 直接套了一个4重循环居然没超时我就呵呵了 //#pragma co ...
-
HDU 4539 郑厂长系列故事——排兵布阵
http://acm.hdu.edu.cn/showproblem.php?pid=4539 郑厂长系列故事——排兵布阵 Time Limit: 10000/5000 MS (Java/Others) ...
随机推荐
-
MySQL数据库小实验
实验1 1.创建数据表 CREATE TABLE guest( Accounts ) NOT NULL, Details ) NOT NULL, Date ) NOT NULL, ,), Class ...
-
PCI设备内存操作函数总结
1. ExAllocatePool() 函数说明: ExAllocatePool allocates pool memory of the specified type and returns a ...
-
linux添加环境变量(path)
分为三步 1.sudo vim /etc/profile 2.export PATH="全路径:$PATH" 3.source /etc/profile 我的微信二维码如下,欢迎交 ...
-
单机版Kubernetes集群(一)
环境:CentOS Linux release 7.4.1708 (Core) 单机版Kubernetes集群的效果,如图: 1)JSP页面通过JDBC直接访问Mysql数据库并展示:这里只是为了 ...
-
T-SQL:函数大全(九)
1.CONCAT函数 SELECT custid, country, region, city, country + N',' + region + N',' + city AS location F ...
-
SpringRMI远程方法调用【原】
Spring为各种远程访问技术的集成提供了工具类. 该小段引用自 http://www.open-open.com/lib/view/open1408957290478.html Spring远程支持 ...
-
JdbcTemplate 方法使用
作者QQ:1095737364 QQ群:123300273 欢迎加入! execute方法:可以用于执行任何SQL语句,一般用于执行DDL语句: update方法及batchUpdate ...
-
【USACO 1.4】Combination Lock
/* TASK:combo LANG:C++ URL:http://train.usaco.org/usacoprob2?a=E6RZnAhV9zn&S=combo SOLVE:自己做,想的是 ...
-
Swift3 JSON字符串和字典互转(JSON字符串转字典和字典转JSON字符串)
直接上代码吧 1.JSONString转换为字典 /// JSONString转换为字典 /// /// - Parameter jsonString: <#jsonString descrip ...
-
Hadoop与Spark之间的比较
Hadoop与Spark之间的比较 Hadoop框架的主要模块包括如下: Hadoop Common Hadoop分布式文件系统(HDFS) Hadoop YARN Hadoop MapReduce ...