Codeforces Gym 100015F Fighting for Triangles 状态压缩DP
F Fighting for Triangles
Description
Andy and Ralph are playing a two-player game on a triangular board that looks like the following:
1 2
3
4 5 7 8
6 9
10 11 13 14 16 17
12 15 18
At each turn, a player must choose two adjacent vertices and draw a line segment that connects them.
If the newly drawn edge results in a triangle on the board (only the smallest ones count), then the player
claims the triangle and draws another edge. Otherwise, the turn ends and the other player plays. The
objective of the game is to claim as many triangles as possible. For example, assume that it is Andy’s turn,
where the board has fives edges as shown in the picture below. If Andy draws edge 6, then he will claim the
triangle formed by edge 4, 5, and 6, and continue playing.
Given a board that already has some edges drawn on it, decide the winner of the game assuming that
both Andy and Ralph play optimally. Andy always goes first. Note that if a triangle exists on the board
before the first move, neither player claims it.
Input
The input consists of multiple test cases. Each test case begins with a line containing an integer N,5 !
N ! 10, which indicates the number of edges that are already present on the board before the game begins.
The next line contains N integers, indicating the indices of these edges. The input terminates with a line
with N = 0. For example:
Output
For each test case, print out a single line that contains the result of the game. If Andy wins, then print out
“Andy wins”. If Ralph wins, then print out “Ralph wins”. If both players get the same number of triangles,
then print out “Draw”. Quotation marks are used for clarity and should not be printed. For example, the
correct output for the sample input above would be:
Sample Input
6
1 2 3 4 5 6
5
4 5 6 7 8
0
Sample Output
Andy wins
Ralph wins
题意:给一个图, 是一个正三角形,在三角形内部(包括边缘)有18个点,每次你可以去相邻的点画一条线段,假如这条线段可以和相邻的点构成一个新的三角形,那么价值+1
现在有两个人玩这个比赛,A先手,假如A不能获取价值 才轮到B 知道所有可能的线段全部画完,问你A,B谁获取的价值更大
开始给你n个点,表示这n个点间有线段已经被画完
题解:电数n<=18我们设定 x为当前被画掉的状态,且f先手
那么 记忆花搜索dp[x][f] 表示就是当前x情况下 f先手 a 取得的价值是多少
爆搜记忆就好
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long ll;
const int N = <<;
int dp[N][],v[];
int cal(int x) {
memset(v,,sizeof(v));
int ret = ;
for(int i = ; i >= ; i--) if(x & (<<i)) v[i + ] = ;
for(int i = ; i <= ; i += ) {
if(v[i] && v[i+] && v[i+]) ret++;
}
if(v[] && v[] && v[]) ret++;
if(v[] && v[] && v[]) ret++;
if(v[] && v[] && v[]) ret++;
return ret;
}
int dfs(int n,int f) {
if(dp[n][f] != -) return dp[n][f];
int last = - cal(n);
dp[n][f] = ;
for(int i = ; i < ; i++) {
if(((<<i) & n) != ) continue;
int nex = n|(<<i);
int g = cal(nex) - cal(n);
if(g) dp[n][f] = max(dp[n][f],dfs(nex,f) + g);
else dp[n][f] = max(dp[n][f], last - dfs(nex,-f));//
}
return dp[n][f];
}
int main() {
int n, x;
memset(dp,-,sizeof(dp));
while(scanf("%d",&n)!=EOF) {
if(n == ) break;
int f = ;
for(int i = ; i <= n; i++) scanf("%d",&x), f |= (<<(x-));
int last = - cal(f);
// for(int i = 1; i <= 18; i++)if(v[i]) printf("1");else cout<<0;
int a = dfs(f,);
int b = last - a;
if(a > b) printf("Andy wins\n");
else if(a == b) printf("Draw\n");
else printf("Ralph wins\n");
}
return ;
}
代码
最新文章
- 【.net 深呼吸】记录WCF的通信消息
- Rust初步(五):Rust与C#性能比较
- Xcode7打包,iOS9真机闪退,如何解决?
- Oracle学习笔记1
- 基于FPGA的通信系统实验
- 1061: [Noi2008]志愿者招募 - BZOJ
- java静态代理,动态代理,cglib代理
- 转化率最高的16个WordPress 电子商务主题
- linux Bash bug修复记录
- Unity3D 游戏开发架构篇 ——性格一流的设计和持久性
- (转载)ANDROID STRINGS.XML 中的特殊字符转义
- 基于JAVA语言的多线程技术
- c++概括
- TargetType Mismatch
- Spark环境搭建(三)-----------yarn环境搭建及测试作业提交
- 关于html引用php文件在编译器正常运行,web浏览器出问题的一点心得
- Web.config设置system.webServer
- docker 入门第一步
- 常用for循环和for in 以及for of 的区别
- [转]Ubuntu python-config