hdu 4753 2013南京赛区网络赛 记忆化搜索 ****

看到范围基本可以想到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 ;
}
上一篇:AngularJs的UI组件ui-Bootstrap分享(十二)——Rating


下一篇:AngularJs的UI组件ui-Bootstrap分享(八)——Tooltip和Popover