看到范围基本可以想到dp了，处理起来有点麻烦
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<string>
5 #include<algorithm>
6 #include<map>
7 #include<queue>
8 #include<stack>
9 #include<cmath>
10 #include<vector>
11 #define inf 0x3f3f3f3f
12 #define Inf 0x3FFFFFFFFFFFFFFFLL
13 #define eps 1e-9
14 #define pi acos(-1.0)
15 using namespace std;
16 typedef long long ll;
17 //edges[i][j]为边(i,j)的编号，marks[i]表示边i是横边还是竖边
18 int edges[30][30],marks[30],p[30];
19 //cont[i]为后添加的边在状态中是多少位，conp[i]为后面的状态中第i位为哪条边
20 int dp[5000],cont[30],conp[30],len;
21 //selected[i]表示第i条边是否在最开始已经选了
22 bool selected[30];
23 void Init()
24 {
25 int cnt=0;
26 memset(edges,0,sizeof(edges));
27 memset(marks,0,sizeof(marks));
28 memset(selected,0,sizeof(selected));
29 for(int i=0;i<5000;++i) dp[i]=-inf;
30 for(int i=1;i<=13;i+=4)
31 {
32 for(int j=0;j<3;++j)
33 {
34 edges[i+j][i+j+1]=edges[i+j+1][i+j]=++cnt;
35 marks[cnt]=1;
36 }
37 if(i==13) break;
38 for(int j=0;j<4;++j)
39 edges[i+j][i+j+4]=edges[i+j+4][i+j]=++cnt;
40 }
41 for(int i=0;i<30;++i) p[i]=1<<i;
42 }
43 inline bool check(int a,int b,int c,int state)
44 {
45 if(!selected[a]&&(p[cont[a]]&state)==0) return false;
46 if(!selected[b]&&(p[cont[b]]&state)==0) return false;
47 if(!selected[c]&&(p[cont[c]]&state)==0) return false;
48 return true;
49 }
50 int getpoints(int e,int now)
51 {
52 int sum=0;
53 int a,b,c;
54 if(marks[e])
55 {
56 a=e-4;b=e-3;c=e-7;
57 if(c>0&&check(a,b,c,now))
58 sum++;
59 a=e+3;b=e+4;c=e+7;
60 if(a<24&&check(a,b,c,now))
61 sum++;
62 }
63 else
64 {
65 a=e-4;b=e-1;c=e+3;
66 if(marks[c]&&check(a,b,c,now))
67 sum++;
68 a=e-3;b=e+1;c=e+4;
69 if(marks[a]&&check(a,b,c,now))
70 sum++;
71 }
72 return sum;
73 }
74 int f(int state)
75 {
76 if(state==p[len]-1) return 0;
77 if(dp[state]!=-inf) return dp[state];
78 dp[state]=0;
79 int tmp=-inf;
80 for(int i=0;i<len;++i)
81 {
82 if((p[i]&state)==0)
83 tmp=max(tmp,getpoints(conp[i],state)-f(p[i]|state));
84 }
85 return dp[state]=tmp;
86 }
87 int main()
88 {
89 //freopen("in.txt","r",stdin);
90 //freopen("out.txt","w",stdout);
91 int t,tcase=0;
92 scanf("%d",&t);
93 while(t--)
94 {
95 tcase++;
96 Init();
97 int n,a,b,e,ans=0,turns=0;
98 scanf("%d",&n);
99 len=24-n;
100 for(int i=0;i<n;++i)
101 {
102 scanf("%d%d",&a,&b);
103 e=edges[a][b];
104 if(turns)
105 ans-=getpoints(e,0);
106 else ans+=getpoints(e,0);
107 turns^=1;
108 selected[e]=true;
109 }
110 int cnt=0;
111 for(int i=1;i<=24;++i)
112 if(!selected[i]) {conp[cnt]=i;cont[i]=cnt;cnt++;}
113 if(turns)
114 ans-=f(0);
115 else ans+=f(0);
116 printf("Case #%d: ",tcase);
117 if(ans>0) puts("Tom200");
118 else puts("Jerry404");
119 }
120 return 0;
121 }