看到范围基本可以想到dp了,处理起来有点麻烦

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
//edges[i][j]为边(i,j)的编号,marks[i]表示边i是横边还是竖边
int edges[][],marks[],p[];
//cont[i]为后添加的边在状态中是多少位,conp[i]为后面的状态中第i位为哪条边
int dp[],cont[],conp[],len;
//selected[i]表示第i条边是否在最开始已经选了
bool selected[];
void Init()
{
int cnt=;
memset(edges,,sizeof(edges));
memset(marks,,sizeof(marks));
memset(selected,,sizeof(selected));
for(int i=;i<;++i) dp[i]=-inf;
for(int i=;i<=;i+=)
{
for(int j=;j<;++j)
{
edges[i+j][i+j+]=edges[i+j+][i+j]=++cnt;
marks[cnt]=;
}
if(i==) break;
for(int j=;j<;++j)
edges[i+j][i+j+]=edges[i+j+][i+j]=++cnt;
}
for(int i=;i<;++i) p[i]=<<i;
}
inline bool check(int a,int b,int c,int state)
{
if(!selected[a]&&(p[cont[a]]&state)==) return false;
if(!selected[b]&&(p[cont[b]]&state)==) return false;
if(!selected[c]&&(p[cont[c]]&state)==) return false;
return true;
}
int getpoints(int e,int now)
{
int sum=;
int a,b,c;
if(marks[e])
{
a=e-;b=e-;c=e-;
if(c>&&check(a,b,c,now))
sum++;
a=e+;b=e+;c=e+;
if(a<&&check(a,b,c,now))
sum++;
}
else
{
a=e-;b=e-;c=e+;
if(marks[c]&&check(a,b,c,now))
sum++;
a=e-;b=e+;c=e+;
if(marks[a]&&check(a,b,c,now))
sum++;
}
return sum;
}
int f(int state)
{
if(state==p[len]-) return ;
if(dp[state]!=-inf) return dp[state];
dp[state]=;
int tmp=-inf;
for(int i=;i<len;++i)
{
if((p[i]&state)==)
tmp=max(tmp,getpoints(conp[i],state)-f(p[i]|state));
}
return dp[state]=tmp;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,tcase=;
scanf("%d",&t);
while(t--)
{
tcase++;
Init();
int n,a,b,e,ans=,turns=;
scanf("%d",&n);
len=-n;
for(int i=;i<n;++i)
{
scanf("%d%d",&a,&b);
e=edges[a][b];
if(turns)
ans-=getpoints(e,);
else ans+=getpoints(e,);
turns^=;
selected[e]=true;
}
int cnt=;
for(int i=;i<=;++i)
if(!selected[i]) {conp[cnt]=i;cont[i]=cnt;cnt++;}
if(turns)
ans-=f();
else ans+=f();
printf("Case #%d: ",tcase);
if(ans>) puts("Tom200");
else puts("Jerry404");
}
return ;
}

最新文章

  1. OpenGL学习进程(13)第十课:基本图形的底层实现及算法原理
  2. pylab模式
  3. Linux Java 环境变量设置
  4. 《Java数据结构与算法》笔记-CH4-5不带计数字段的循环队列
  5. 最大流&amp;最小割 - 专题练习
  6. Stimulsoft Reports报表工具
  7. Angular简单应用剖析
  8. [io PWA] Great libraries and tools for great Progressive Web Apps
  9. [Fw]人和人之间在八小时之外的差别
  10. nginx,php日志分割
  11. php中memcache的运用
  12. 1020关于MYCAT的安装和使用总结
  13. 山西大同大学教务处教师端——可在PC端,手机端操作
  14. ABAQUS/CAE——Context
  15. python学习第22天
  16. 20165206 2017-2018-2 《Java程序设计》第9周学习总结
  17. CodeBlock 快捷键大全
  18. vbs调用bat 隐藏bat运行时的黑框
  19. uva-10887-枚举
  20. Anfroid 在界面中显示图片 ImageView

热门文章

  1. BZOJ 1041
  2. $.extend() 或 jQuery.extend() 与 $.fn.Xxx 或 jQuery.fn.extend(object) 之jQuery插件开发
  3. 转:jQuery弹出二级菜单
  4. EOS单向N对1关联
  5. 转帖:用五分钟重温委托,匿名方法,Lambda,泛型委托,表达式树
  6. Nodejs 及 NPM 的安装
  7. Wijmo 5 与Breeze 的组合,及与METRONIC 的集成
  8. Java集合中Set的常见问题及用法
  9. DB2中错误信息说明
  10. 【XLL 框架库函数】 Excel/Excel12f