算法
(博弈型DP) $O(NK)$
记 dp[i]
表示还剩下 $i$ 个石子时,先手是否必胜
显然,$\operatorname{dp}[0]$ 表示先手必输
然后考虑当前剩石子数的所有后继状态中是否存在必输状态,那么把它留给对方就行了,此时可以做到先手必胜;反之,如果后继状态都是必胜态的话,那么不管怎么做都会把必胜态交给对方,所以先手必输
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> dp(k+1);
for (int i = 1; i <= k; ++i) {
rep(j, n) if (i >= a[j]) {
dp[i] |= !dp[i-a[j]];
}
}
puts(dp[k] ? "First" : "Second");
return 0;
}