博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ1143 Number Game(DP)
阅读量:4837 次
发布时间:2019-06-11

本文共 1075 字,大约阅读时间需要 3 分钟。

题目大意:

就是说两个人交换选一些数,如果a,b被选过了,那么k*a+m*b(k,m >=0 )这样的数就不能再被选择,现在给你一些还没有选的数,问选哪个数可以使你必胜

如样例:

2 5

如果你选2,由于3已经选过了,而2+3=5,所以5也不能备选择。所以选2就为必胜的选择

我的思路:

,这道题的最初要想到的就是,由于题目的给的数的范围很小,<=20。所以表示这些数的集合就可以用二进制模拟。

用一个DP数组就可以存下,他有两个值就是0和1,表示必胜和必输两个状态。详见代码:

 

1 #include 
2 #include
3 #include
4 #include
5 #define MAX(a,b) (a) > (b)? (a):(b) 6 #define MIN(a,b) (a) < (b)? (a):(b) 7 #define mem(a) memset(a,0,sizeof(a)) 8 #define INF 1000000007 9 #define MAXN 1<<2010 #define MACN 2011 12 #define JUDGE (((1<<(ma[j]-ma[i]-1)) & ~st) &&(ma[j]-ma[i] != 1)) || (!((ma[j]+1)%(ma[i]+1)))13 14 using namespace std;15 16 int DP[MAXN],ma[MACN],vis[MAXN];17 int N;18 19 int search(int k,int state)20 {21 if(vis[state])return DP[state];22 vis[state]=1;23 if(state == 0)return 0;24 if(k == 1)return DP[state] = 1;//集合里面只有一个数了,一定是必胜状态25 int i, j, key=0;26 for(i = 0;i < N;i ++ )27 {28 int st = state;29 if((1<

 

转载于:https://www.cnblogs.com/gj-Acit/archive/2013/06/05/3118977.html

你可能感兴趣的文章
导航条选项卡
查看>>
bootstrap table 复选框使用
查看>>
ng -v 不是内部或外部命令
查看>>
图片模糊化处理
查看>>
iOS10 App适配权限 Push Notifications 字体Frame 遇到的坑!!!!
查看>>
一语道破项目管理知识体系五大过程组
查看>>
Mac连接远程Linux管理文件(samba)
查看>>
WPF变换详解
查看>>
flash player 请求本地存储为无限制
查看>>
程序逻辑的组织方式
查看>>
今天正式开通博客
查看>>
javascript逗号添加函数
查看>>
Codeforces Round #307 (Div. 2) E. GukiZ and GukiZiana 分块
查看>>
hdu 5452 Minimum Cut 树形dp
查看>>
perf4j @Profiled常用写法
查看>>
配置的热更新
查看>>
ios view的frame和bounds之区别(位置和大小)
查看>>
Spark Streaming笔记整理(三):DS的transformation与output操作
查看>>
全面对比微服务配置中心,哪一个更适合你?
查看>>
C++的正则
查看>>