P9911 [COCI 2023/2024 #2] Kuglice 题解
zjpwwc
·
·
题解
P9911 Kuglice 题解
前言：
-
第一次写题解，有写的不好的地方可以私信我指出，谢谢。
-
题目难度估计在 绿。
题目大意：
题意很好懂，看两个人谁第一次拿走某种颜色的球，输出比分。
题目思路：
我们可以把这个双端队列看作一个 长度为 n 的区间，这个大区间可以划分成很多个 小区间。
首先：编号为 a_i 的球在哪段区间拿会得到一分？
注：题目说了两端都能拿球。
其实很简单，我们假定一个区间 [l,r]，如果编号为 a_i 的球第一次出现在 2 号位，最后一次出现在 10 号位，区间为 [4,7]，那么这个球早在 4 号位的前面或者 7 号位的后面拿过了。原因是区间最左边和最右边的外面就有 想要的球 了。
如果区间 [l,r] 不能把编号为 a_i 的球 第一次出现的位置 和 最后一次出现的位置 囊括。那么这一段区间一定不能得分。
这一步，我们只需要记录每种球 第一次出现的位置 和 最后一次出现的位置，判断区间 [l,r] 是否囊括球的位置即可。
其次：怎样拿球双方都最优？
使用记忆化和 DP。
什么叫加分？
如果 $k$ 种球的话，双方加起来就是 $k$ 分。
你在队列里拿球比对手会多的分数就是加分（**加分可能是负数**）。
小学数学告诉我们，总分为 $k$，你比对手多 $a$，你的分数就是 $\large \frac{k + a}{2}$。
现在，我们知道，球数是 $k$，加分为 $dp_{1,n}$。
所以，我们求 $\large \frac{k + dp_{1,n}}{2}$ 就行了。
现在我们来看如何求 DP。
DP 思路很简单，**从左边拿和从右边** 拿哪样贡献大，求 $\max$ 再转移就行。
这时有人会说一个大状态就有两个小状态, $n$ 最大 $1000$，这样跑搜索数时间复杂度大概是 $4^n$ 级别,会爆。
确实，但我们可以用记忆化来优化，一开始赋一个极小的初值，如果跑搜索数跑到这里发现 **初始值没有更新**，说明这条路不能给我们带来贡献，从而返回上一级。
#### 状态转移方程归纳
```
dp[l][r] = max(check(l, r, k[l]) - del(l+1, r), check(l, r, k[r]) - del(l, r-1)));
```
`check()` 就是检查第一步的合法性，如果合法就返回 $1$，分数 $+1$，如果不合法就返回 $0$，分数不变。
`del()` 就是递归函数，计算 $dp_{l,r}$ 的。
有些地方可能你没看懂，这里给上参考代码帮助你理解，代码也有注释。
---
## 参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int len=3e3+10;
int INF=1<<31;
int n,cnt,a,b;
int k[len],lid[len],rid[len],dp[len][len];
int check(int l,int r,int k){
return lid[k]>=l&&rid[k]<=r;//检查区间合法性
}
int del(int l,int r){
if(l>r) return 0;
if(dp[l][r]==INF) dp[l][r]=max(check(l,r,k[l])-del(l+1,r),check(l,r,k[r])-del(l,r-1));
return dp[l][r];
}//带剪枝的递归
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>k[i];
if(!lid[k[i]]){
cnt++;//球的种类数
lid[k[i]]=i;//第一次出现的位置
}
rid[k[i]]=i;//最后一次
}
fill(dp[0],dp[0]+len*len,INF);//初始化极小值
del(1,n);//开始递归
a=(cnt+dp[1][n])/2;
b=cnt-a;
printf("%d:%d",a,b);//计算比分
return 0;
}
``````
* * *
## 总结：
一道不错的思维题，做法也很灵活，有不懂可以私信我，谢谢大家。