Mondriaan's Dream POJ - 2411
2024-09-08 00:33:38
可以用状压dp，但是要打一下表。暴力枚举行、这一行的状态、上一行的状态，判断如果上一行的状态能转移到这一行的状态就转移。
状态定义：ans[i][S]表示i行前已经全部填满，i行已经填上的列为集合S。如果有竖着的，全部当做用这一行的去补满上一行缺的。
（貌似还是插头dp的入门题）
#include<cstdio>
#include<cstring>
typedef long long LL;
LL f[][];
LL h,w;
/*LL ans[12][2050];
LL h,w;
bool judge(LL a,LL b)
{
LL i,num=0,t1,t2;
for(i=1;i<=w;i++)
{
t1=a&1;
t2=b&1;
a>>=1;
b>>=1;
if(t1==1&&t2==1)
num++;
else if(t1==0&&t2==0)
return false;
else
{
if(num&1)
return false;
num=0;
}
}
if(num&1)
return false;
else
return true;
}
LL get(LL h,LL w)
{
LL i,j,k;
memset(ans,0,sizeof(ans));
ans[0][(1<<w)-1]=1;
for(i=1;i<=h;i++)
for(j=0;j<(1<<w);j++)
for(k=0;k<(1<<w);k++)
if(judge(k,j))
{
ans[i][j]+=ans[i-1][k];
}
return ans[h][(1<<w)-1];
}
int main()
{
for(h=1;h<=11;h++)
for(w=1;w<=11;w++)
printf("f[%lld][%lld]=%lld;\n",h,w,get(h,w));
return 0;
}*/
int main()
{
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
scanf("%lld%lld",&h,&w);
while(h!=&&w!=)
{
printf("%lld\n",f[h][w]);
scanf("%lld%lld",&h,&w);
}
}
最新文章
- 微信扫码i支付~官方DEMO的坑
- 深入理解CSS盒子模型
- 大熊君学习html5系列之------requestAnimationFrame（实现动画的另一种方案）
- 引入HBase依赖包带来的麻烦
- 23Spring_JdbcTemplate来实现单表的增删改查
- Java集合类之栈Stack
- RestKit：iOS开发必备，告别众多无聊代码
- OOX 面向对象X
- PHP面向对象 ——多态
- String,StringBuffer,StringBuilder的区别及其源码分析
- Salesforce Lightning开发学习（二）Component组件开发实践
- Self Host 使用 Exceptionless 实时监控程序运行日志服务
- linux expect 即exp脚本交互功能【原】
- SpringBoot入门教程(一)详解intellij idea搭建SpringBoot
- REST构架风格介绍之一：状态表述转移
- mysql索引学习
- ES6 HttpApplication Middleware
- Windows系统中Xshell与Linux连接时遇到的问题
- Qt creator 使用qwt
- 为什么vue+webpack需要用到node，如何部署项目到服务器？