poj 2068 Nim 博弈论
2024-10-18 19:26:09
思路:dp[i][j]:第i个人时还剩j个石头。
当j为0时,有必胜为1;
后继中有必败态的为必胜态!!记忆化搜索下就可以了!
代码如下:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define inf 1e9
using namespace std;
int dp[][],n,a[];
int dfs(int d,int s)
{
if(dp[d][s]!=-) return dp[d][s];
if(s==) return dp[d][s]=;
dp[d][s]=;
for(int i=;i<=a[d]&&i<=s;i++)
if(!dfs((d+)%(*n),s-i))
dp[d][s]=;
return dp[d][s];
}
int main()
{
int i,j,q,k,t,s;
while(scanf("%d",&n)&&n){
scanf("%d",&s);
memset(dp,-,sizeof(dp));
for(i=;i<*n;i++) scanf("%d",&a[i]);
printf("%d\n",dfs(,s));
}
return ;
}
最新文章
- 网页JQ基础之jq-隐藏以及显示特效
- sqlite3使用(一)
- Windows下mysql自动备份的最佳方案
- 杭JS
- 51中的C语言数据类型
- Android单元测试: 首先,从是什么开始
- myEclipse勿删文件怎么恢复
- Java Persistence with MyBatis 3(中国版) 第五章 与Spring集成
- SD卡读写扇区注意事项(转)
- js document
- Html +++++css总结
- mpvue——另类支持v-html
- Python——scapy模块实现tcp探测目标服务器路由轨迹
- 与虚拟机连接出现ora-12514错误解决方法
- POJ2279杨氏矩阵+钩子定理
- R中执行if else报错:unexpected &#39;else&#39; in ";else";
- 【BZOJ5334】数学计算(线段树)
- .NET类库
- 单片机关键字sfr和sbit的理解
- If you want the rainbow, you have to deal with the rain.