状态压缩dp解博弈问题(记忆化搜索)。比赛的时候最后才开始做这道题,而且当时不知道为什么一直犯一些很2B的问题,导致没能ac,晚上看了看原先的代码,改了一下就MLE了。。。我原先是开的dp[1 << 24] 的记忆化数组,果断超内存了,然后仔细看了一下题目,发现题目中的n >= 12,也就是说用到的状态不超过2^12个,于是把满足情况的状态hash到2^12以内的数组就可以了。
思路:
因为只有24条边,所以可以考虑把边压缩,于是就转化成了普通的状态了,然后用dp数组表示该状态下先手能得到的最大分值。也就是处于该状态时,先手放一条边以后得使得后手得分最少,因为总分是一定的,这样的话先手就可以得到最优解了。然后就记忆化搜索一下就可以了。我hash用的是数组存储,二分查找下标的方法,时间效率不是很高。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
using namespace std;
const int N= 1 << 13;
const int INF = 1e9;
int dp[N], n, mp[N];
int gogo[22][22], num;
void get_gogo()
{
int i , j = 0;
for(i = 1; i < 16; i ++)
{
if(i % 4 == 0) continue;
gogo[i][i + 1] = j;
j ++;
}
for(i = 1; i <= 12; i ++)
{
gogo[i][i + 4] = j;
j ++;
}
}
bool ok(int k, int i)
{
return (k & (1 << i)) && (k & (1 << (i + 3))) && (k & (1 << ((i / 3) + i + 12))) && (k & (1 << ((i / 3) + i + 13)));
}
int get_f(int k)
{
int i, j, ret = 0;
for(i = 0; i < 9; i ++)
{
if((k & (1 << i)) && ok(k, i))
ret ++;
}
return 9 - ret;
}
int B_ser(int k)
{
int l = 0, r = num - 1, m;
while(l <= r)
{
m = (l + r) >> 1;
if(mp[m] == k) return m;
else if(mp[m] > k) r = m -1;
else l = m + 1;
}
}
int dfs(int mk)
{
int k = mp[mk];
if(dp[mk] != -1) return dp[mk];
int ret = INF, i;
for(i = 0; i < 24; i ++)
{
if(((1 << i) & k) == 0)
{
ret = min(ret, dfs(B_ser(k | (1 << i))));
}
}
if(ret == INF)
{
return dp[mk] = get_f(k);
}
return dp[mk] = get_f(k) - ret;
}
int main()
{
//freopen("input.txt", "r", stdin);
int a, b, n, u, v, i, j, t, cas = 1, tt, now;
get_gogo();
scanf("%d", &tt);
while(tt --)
{
scanf("%d", &n);
CLR(dp, -1);
t = a = b = 0;now = 0;
for(i = 0; i < n; i ++)
{
scanf("%d%d", &u, &v);
if(u > v) swap(u, v);
int tmd = gogo[u][v];
t += (1 << tmd);
int kao = 9 - get_f(t);
if(i & 1)
{
b += kao - now;
now = kao;
}
else
{
a += kao - now;
now = kao;
}
}
for(i = t, num = 0; i < (1 << 24); i ++)
{
if((i & t) == t)
{
mp[num ++] = i;
}
}
if(n & 1)
{
b += dfs(0);
printf("Case #%d: %s\n", cas ++, b > (9 - b) ? "Jerry404" : "Tom200");
}
else
{
a += dfs(0);
printf("Case #%d: %s\n", cas ++, a < (9 - a) ? "Jerry404" : "Tom200");
}
}
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码