P7928 [COCI2021-2022#1] Kamenčići

2023-10-10 07:20

文章标签 2022 kamen coci2021 p7928

本文主要是介绍P7928 [COCI2021-2022#1] Kamenčići，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P7928 [COCI2021-2022#1] Kamenčići

[P7928 COCI2021-2022#1] Kamenčići - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

文章目录

P7928 [COCI2021-2022#1] Kamenčići
- 题目大意
- 思路
- code

题目大意

Alice 和 Bob 又在玩游戏。

在他们面前有 $n$ 块石头排成一行，石头有红和蓝两种颜色。

Alice 先手，每次每人从两端选择一端取出一块石头，谁先取出 $k$ 块红色石头谁输掉。

假设 Alice 和 Bob 都是绝顶聪明的，求出最后谁获胜。

思路

记忆化搜索

设 $f [l] [r] [k]$ 表示现在区间是 $[l, r]$ ，现在先手有 $k$ 块红石子的胜负。

$s u m 1, s u m 2$ 分别为前缀和、后缀和。

那么对方手上的石子数就为 $s u m 1 [l - 1] + s u m 2 [r + 1] - k$

每次特判 $sum1[l - 1] + sum2[r + 1] - k $ 有没有大于 $K$

设 $v a l = s u m 1 [l - 1] + s u m 2 [r + 1]$

那么 $KaTeX parse error: Undefined control sequence: \or at position 32: …l + 1][r][val] \̲o̲r̲ ̲f[l][r - 1][val…$

答案就是 $f [1] [n] [0]$

code

#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;
}