65 数学游戏
动态规划
#include <iostream>
#include <vector>using namespace::std;
using std::cout;
using std::cin; vector<int> use;int dfs(int now,int maxChoosableInteger,int desiredTotal)
{if(use[now] != 0) {return use[now]==1;}int res=0;for(int i=maxChoosableInteger; i>0; i--){int cur = 1<<(i-1);if((now & cur) != 0) {continue;} if(i >= desiredTotal || !dfs(now|cur,maxChoosableInteger,desiredTotal-i)){res=1;break;}}use[now] = (res==true ? 1 : 2);return res;}int sxyx(int maxChoosableInteger, int desiredTotal)
{if(maxChoosableInteger >= desiredTotal) {return 1;}if(maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal) {return 0;}use = vector<int>(1<<maxChoosableInteger,0);return dfs(0,maxChoosableInteger,desiredTotal);}int main()
{int maxChoosableInteger,desiredTotal;cin >> maxChoosableInteger >> desiredTotal;if(sxyx(maxChoosableInteger,desiredTotal) == 1){std::cout << "true";}else{std::cout << "false";}return 0;
}