【BZOJ】3895: 取石子
2024-10-19 12:40:36
【算法】博弈论+记忆化搜索
【题意】给定n堆石子,两人轮流操作,每个人可以合并两堆石子或拿走一个石子,不能操作者输,问是否先手必胜
【题解】
首先,若所有石子堆的石子数>1,显然总操作数为(石子数+石子堆数-1),奇数先手必胜,偶数先手必败。
若有部分石子堆的石子数=1,情况较复杂,考虑一下五种情形:
1. 拿走石子数=1的石子堆
2.减少操作次数(拿走石子或合并石子堆)
3.操作数减至1时,视为多一堆石子数=1的石子堆(若操作数不为1,即使出现也会被再次操作抵消)
4.合并两个石子数=1的石子堆
5.合并一个石子数=1和一个石子数>1的石子堆
对于(石子数=1的石子堆数(<=50),总操作数(<=50049))二元组进行记忆化搜索。(记忆化是针对所有数据的统一记忆化,这样50*50049就不会超时)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,a[],f[][];
int dfs(int x,int y)
{
if(~f[x][y])return f[x][y];
if(x==)return y&;
if(y==)return dfs(x+,);//
if(x&&!dfs(x-,y))return f[x][y]=;
if(y&&!dfs(x,y-))return f[x][y]=;
if(x>&&!dfs(x-,y++(y?:)))return f[x][y]=;
if(x&&y&&!dfs(x-,y+))return f[x][y]=;
return f[x][y]=;
}
int main()
{
int T;
scanf("%d",&T);
memset(f,-,sizeof(f));
while(T--)
{
scanf("%d",&n);
//memset(f,-1,sizeof(f));
int tmp=,sum=;
for(int i=;i<=n;i++){scanf("%d",&a[i]);if(a[i]==)tmp++;else sum+=a[i];}
if(dfs(tmp,n-tmp-+sum))printf("YES\n");else printf("NO\n");
}
return ;
}
最新文章
- GIS公交查询-flex/java
- Memcached深度分析
- [CareerCup] 2.6 Linked List Cycle 单链表中的环
- 网易新闻页面信息抓取 -- htmlagilitypack搭配scrapysharp
- BootStrap2学习日记16---选项卡内容
- Delphi单元文件之-防止程序重复执行
- linux Ubuntu安装后没有引导 解决方案
- 关于MD5校验和java工程下的校验
- Solr4.6从数据库导数据的步骤
- TreeSet具体应用
- 共享bean
- nodejs - json序列化&;反序列化示例
- hdu 1859 最小长方形
- HP-Socket快速入门:分包、粘包解析
- java8新特性-默认方法
- Golang入门教程(二)Ubuntu16.04下安装golang(实例:Golang 定时任务管理器)
- [matlab] 1.拟合
- 【Luogu4921】情侣?给我烧了!(组合计数)
- 缓慢变化维 (Slowly Changing Dimension) 常见的三种类型及原型设计(转)
- Java如何格式化AM-PM格式的时间?