【DP】 POJ 1085 Triangle War
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <time.h>
#define maxn 300005
#define maxm 400005
#define eps 1e-7
#define mod 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#define lowbit(x) (x&(-x))
#define mp make_pair
#define ls o<<1
#define rs o<<1 | 1
#define lson o<<1, L, mid
#define rson o<<1 | 1, mid+1, R
#define pii pair<int, int>
#pragma comment(linker, "/STACK:16777216")
typedef long long LL;
typedef unsigned long long ULL;
//typedef int LL;
using namespace std;
LL qpow(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base;base=base*base;b/=2;}return res;}
LL powmod(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base%mod;base=base*base%mod;b/=2;}return res;}
// head
int o = (1 << 18) - 1;
int dp[maxn][2];
int a[maxn];
int c[maxn];
int m, s, ss, res;
void init()
{
a[0] = (1 << 0) | (1 << 1) | (1 << 2);
a[1] = (1 << 3) | (1 << 4) | (1 << 7);
a[2] = (1 << 4) | (1 << 5) | (1 << 2);
a[3] = (1 << 5) | (1 << 6) | (1 << 8);
a[4] = (1 << 9) | (1 << 10) | (1 << 15);
a[5] = (1 << 7) | (1 << 10) | (1 << 11);
a[6] = (1 << 11) | (1 << 12) | (1 << 16);
a[7] = (1 << 12) | (1 << 13) | (1 << 8);
a[8] = (1 << 13) | (1 << 14) | (1 << 17);
a[9] = (1 << 0) | (1 << 3) | (1 << 1) | (1 << 6) | (1 << 7) | (1 << 8);
for(int i = 0; i <= o; i++)
for(int j = 0; j < 9; j++)
if((i & a[j]) == a[j]) c[i]++;
memset(dp, INF, sizeof dp);
}
void read()
{
scanf("%d", &m);
res = ss = 0;
int t = 0, aa, bb, t2 = 0;
for(int i = 0; i < m; i++) {
scanf("%d%d", &aa, &bb);
if(aa > bb) swap(aa, bb);
if(aa == 1) {
if(bb == 2) t |= (1 << 0);
if(bb == 3) t |= (1 << 1);
}
if(aa == 2) {
if(bb == 3) t |= (1 << 2);
if(bb == 4) t |= (1 << 3);
if(bb == 5) t |= (1 << 4);
}
if(aa == 3) {
if(bb == 5) t |= (1 << 5);
if(bb == 6) t |= (1 << 6);
}
if(aa == 4) {
if(bb == 5) t |= (1 << 7);
if(bb == 7) t |= (1 << 9);
if(bb == 8) t |= (1 << 10);
}
if(aa == 5) {
if(bb == 6) t |= (1 << 8);
if(bb == 8) t |= (1 << 11);
if(bb == 9) t |= (1 << 12);
}
if(aa == 6) {
if(bb == 9) t |= (1 << 13);
if(bb == 10) t |= (1 << 14);
}
if(aa == 7) t |= (1 << 15);
if(aa == 8) t |= (1 << 16);
if(aa == 9) t |= (1 << 17);
if(!ss) res += c[t] - c[t2];
else res -= c[t] - c[t2];
if(!(c[t] - c[t2])) ss ^= 1;
t2 = t;
}
s = t;
}
int dfs(int now, bool flag)
{
if(dp[now][flag] != INF) return dp[now][flag];
if(now == o) return dp[now][flag] = 0;
int ans;
if(flag) ans = -INF;
else ans = INF;
for(int i = 0; i < 18; i++) {
if((now & (1 << i)) == (1 << i)) continue;
int next = now | (1 << i);
if(c[next] == c[now]) {
if(flag) ans = max(ans, dfs(next, 0));
else ans = min(ans, dfs(next, 1));
}
else {
if(flag) ans = max(ans, dfs(next, 1) + c[next] - c[now]);
else ans = min(ans, dfs(next, 0) - (c[next] - c[now]));
}
}
return dp[now][flag] = ans;
}
void work()
{
res += dfs(s, ss ^ 1);
if(res > 0) printf("A wins.
");
else printf("B wins.
");
}
int main()
{
init();
int _, __ = 0;
while(scanf("%d", &_)!=EOF) {
__ = 0;
while(_--) {
read();
printf("Game %d: ", ++__);
work();
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.