P7928 Kamenčići 解题思路
Kawaii_qiuw
·
·
题解
题目大意
Alice 和 Bob 又在玩游戏。
在他们面前有 n 块石头排成一行，石头有红和蓝两种颜色。
Alice 先手，每次每人从两端选择一端取出一块石头，谁先取出 k 块红色石头谁输掉。
假设 Alice 和 Bob 都是绝顶聪明的，求出最后谁获胜。
解题思路
记忆化搜索。
设 f_{l,r,k} 表示现在区间是 [l,r]，现在先手有 k 块红石子的胜负。
那么对方手上的石子数就为 $sum1_{l - 1} + sum2_{r + 1} - k$。
每次特判 $sum1_{l - 1} + sum2_{r + 1} - k$ 有没有大于 $K$。
设 $val \to sum1_{l − 1} + sum2_{r + 1}$。
那么答案就是 $f_{1,n,0}$。
### 代码
```
#include <bits/stdc++.h>
using namespace std;
int n , k , b[351] , a[351] , sum1[351] , sum2[351] , dp[351][351][351];
char c;
int dfs (int l , int r, int s) {
if (sum1[l - 1] + sum2[r + 1] - s == k) return dp[l][r][s] = 2;
if (dp[l][r][s]) return dp[l][r][s];
int ans1 , ans2;
ans1 = dfs (l + 1 , r , sum1[l - 1] + sum2[r + 1] - s);
ans2 = dfs (l , r - 1 , sum1[l - 1] + sum2[r + 1] - s);
return dp[l][r][s] = (ans1 == 1 || ans2 == 1) ? 2 : 1;
}
int main () {
scanf ("%d%d" , &n , &k);
for (int i = 1 ; i <= n ; i ++) {
c = getchar ();
while (c != 'C' && c != 'P') c = getchar ();
a[i] = (c == 'C');
}
for (int i = 1 ; i <= n ; i ++) sum1[i] = sum1[i - 1] + a[i];
for (int i = n ; i >= 1 ; i --) sum2[i] = sum2[i + 1] + a[i];
puts (dfs (1 , n , 0) == 2 ? "DA" : "NE");
return 0;
}
```
[AC 记录。](https://www.luogu.com.cn/record/197011111)
完结撒花。