我等蒟蒻只能想到石子数 ≥ 2时的情况。。。1的时候就爆搜？大概是这个意思
最后再记忆化一下
1 /************************************************************** 2 Problem: 3895 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:500 ms 7 Memory:12524 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 13 using namespace std; 14 15 int n; 16 int f[60][50005]; 17 18 int dfs(int a, int b) { 19 if (!a) return b & 1; 20 if (b == 1) return dfs(a + 1, 0); 21 if (~f[a][b]) return f[a][b]; 22 if ((a && !dfs(a - 1, b)) || (a && b && !dfs(a - 1, b + 1)) || (a >= 2 && !dfs(a - 2, b + 2 + (b > 0))) || (b && !dfs(a, b - 1))) return f[a][b] = 1; 23 return f[a][b] = 0; 24 } 25 26 int main() { 27 int T, i, a, b, x; 28 memset(f, -1, sizeof(f)); 29 scanf("%d", &T); 30 while (T--) { 31 scanf("%d", &n); 32 for (i = 1, a = 0, b = -1; i <= n; ++i) { 33 scanf("%d", &x); 34 if (x == 1) ++a; 35 else b += x + 1; 36 } 37 if (b == -1) b = 0; 38 puts(dfs(a, b) ? "YES" : "NO"); 39 } 40 return 0; 41 }