题解：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]$。

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

$f[i][j]=\max(cc(i,j,a[i])-f[i+1][j],cc(i,j,a[j])-f[i][j-1])$ ; 其中， cc(i,j,k)表示计算在 $[i,j]$ 内取走颜色为k的球的得分。