题目: Petya and Spiders
传送门:

http://codeforces.com/problemset/problem/111/C

http://codeforces.com/problemset/problem/112/E
分析:
(1)由n·m<=40可以想到状态压缩动态规划,方程很好想,用四进制表示状态,用位运算优化。
(2)由n·m<=40可以想到分类构造公式。
代码:

1)

#include<cstdio>
#include<algorithm>
#define inf 2147483647
int n,m,statenum;
int num[],f[][];
bool pd(int state1,int state2){
int a1=state1%,b1=,c1=,a2=state2%,b2=,c2=;
state1/=;state2/=;
for(int i();i<=*n;i+=){
c1=b1;b1=a1;a1=state1%;state1/=;
c2=b2;b2=a2;a2=state2%;state2/=;
if(b2== && b1!=)return false;
if(b1== && b2!=)return false;
if(b1== && a1!= && c1!=)return false;
}
return true;
}
void solve(){
statenum=(<<n*)-;
for(int i();i<=statenum;++i)
{f[][i]=inf;for(int j=i;j;j>>=)num[i]+=(j&)==;}
f[][statenum]=;
int x=,y=;
for(int k();k<=m+;++k,x=!x,y=!y)
for(int i();i<=statenum;++i){
f[y][i]=inf;
for(int j();j<=statenum;++j)
if(f[x][j]!=inf && pd(i,j))
f[y][i]=std::min(f[y][i],f[x][j]+num[i]);
}
if(f[y][]==inf)
printf("");else printf("%d",n*m-f[x][]);
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d %d",&n,&m);
if(n>m)std::swap(n,m);
solve();
//fclose(stdin);fclose(stdout);
return ;
}

2)

#include<cstdio>
#define P(x) return printf("%d\n",m*n-(x)),0;
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
if(n>m)n^=m,m^=n,n^=m;
switch(n){
case :P((m+)/)
case :P((m+)/)
case :P(m/*+(m%=)+(m==))
case :P(m+(m==||m==||m==))
case :P(m/*-(m==)+(m%=)++(m>))
case :P()
}
fclose(stdin);fclose(stdout);
}

最新文章

  1. Visual Studio插件
  2. BZOJ 1925[Sdoi2010]地精部落 题解
  3. [Python正则表达式] 字符串中xml标签的匹配
  4. 转 Android学习 之 ColorStateList按钮文字变色
  5. 转数据库分库分表(sharding)系列(二) 全局主键生成策略
  6. Dynamics AX 2012 R2 Service Middle Tier WCF WCF转发
  7. 【JavaScript】JS的启动机制
  8. HDOJ --- 1258
  9. LeetCode——Remove Duplicates from Sorted Array
  10. Hello ReactJS
  11. tensorflow rnn 最简单实现代码
  12. Vue.js环境配置
  13. atitit 读书与获取知识资料的attilax的总结.docx
  14. 理解OpenShift(3):网络之 SDN
  15. python3.4学习笔记(十九) 同一台机器同时安装 python2.7 和 python3.4的解决方法
  16. Date类型之继承方法
  17. Lunix/Mac下根据最后修改时间复制文件和文件夹,保持原有的目录结构
  18. ubuntu 安装 codelite
  19. jQuery动态创建的dom对象不能绑定事件的解决方法
  20. 运维小知识之nginx---nginx配置Jboss集群负载均衡

热门文章

  1. IDF-CTF-不难不易的js加密 writeup
  2. Quartz-第一篇 认识Quartz
  3. [BZOJ 1503]郁闷的出纳员(fhq treap)
  4. 使用redis来存储session,不同框架对session的命名规则是不一样的
  5. python学习第十一天列表的分片和运算
  6. beeline链接hive报错
  7. P4195 【模板】exBSGS/Spoj3105 Mod
  8. StatusStrip 分类: C# 2015-07-23 11:58 2人阅读 评论(0) 收藏
  9. 相对路径 分类: C# 2015-06-11 15:41 8人阅读 评论(0) 收藏
  10. 攻防世界--open-source