codeforces 111C/112E Petya and Spiders
2024-09-01 10:19:50
题目: 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);
}
最新文章
- Visual Studio插件
- BZOJ 1925[Sdoi2010]地精部落 题解
- [Python正则表达式] 字符串中xml标签的匹配
- 转 Android学习 之 ColorStateList按钮文字变色
- 转数据库分库分表(sharding)系列(二) 全局主键生成策略
- Dynamics AX 2012 R2 Service Middle Tier WCF WCF转发
- 【JavaScript】JS的启动机制
- HDOJ --- 1258
- LeetCode——Remove Duplicates from Sorted Array
- Hello ReactJS
- tensorflow rnn 最简单实现代码
- Vue.js环境配置
- atitit 读书与获取知识资料的attilax的总结.docx
- 理解OpenShift(3):网络之 SDN
- python3.4学习笔记(十九) 同一台机器同时安装 python2.7 和 python3.4的解决方法
- Date类型之继承方法
- Lunix/Mac下根据最后修改时间复制文件和文件夹,保持原有的目录结构
- ubuntu 安装 codelite
- jQuery动态创建的dom对象不能绑定事件的解决方法
- 运维小知识之nginx---nginx配置Jboss集群负载均衡
热门文章
- IDF-CTF-不难不易的js加密 writeup
- Quartz-第一篇 认识Quartz
- [BZOJ 1503]郁闷的出纳员(fhq treap)
- 使用redis来存储session,不同框架对session的命名规则是不一样的
- python学习第十一天列表的分片和运算
- beeline链接hive报错
- P4195 【模板】exBSGS/Spoj3105 Mod
- StatusStrip 分类: C# 2015-07-23 11:58 2人阅读 评论(0) 收藏
- 相对路径 分类: C# 2015-06-11 15:41 8人阅读 评论(0) 收藏
- 攻防世界--open-source