题解：P9911 [COCI 2023/2024 #2] Kuglice

· · 题解

题目大意：

很好理解，就是问两个人拿球，谁先拿某种颜色谁加分，求分数。

解析：

我们可以用区间DP解题。 先设一个数组f[i][j]表示取完区间[i,j]内的球，先手比后手多出来的分数。

再设shu表示总共能得到的分数，那么根据小学知识，先手能得到的总分就是(shu+f[1][n])/2，后手能得到的总分就是shu-(shu+f[1][n])/2。

然后，再设两个数组shou[i]和wei[i]，表示i元素出现的最早和最晚位置，因为取i元素只能在这两个位置取。

接下来来看状态转移方程。因为只能在左右两端取球，所以f[i][j]的状态转移只能跟f[i+1][j]和f[i][j-1]有关。

并且，之前说过取i元素只能在这最早和最晚位置取，所以，只要满足 shou[a[i]] \ge i && wei[a[i]] \le j ，第i个球的颜色就一定只在区间内出现过。

假设先手取走了 i 号球，那么对于区间 [i+1,j] ，先手就变成了原来的后手，所以应该用取走i号球的得分减去 f[i+1][j] 。

先手取走了j号球也同理：对于区间 [i,j-1] ，先手也变成了原来的后手，所以应该用取走 j 号球的得分减去f[i][j-1]。

这样，我们就得到了如下状态转移方程：

其中， ```cc(i,j,k)```表示计算在 $[i,j]$ 内取走颜色为k的球的得分。