自动搬运

查看原文

来自洛谷，原作者为

	zjpwwc 不拿蓝钩不改个签||CSP-S/NOIP 2025顶峰相会

搬运于2025-08-24 22:52:58，当前版本为作者最后更新于2023-12-22 20:43:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P9911 Kuglice 题解

前言：

1. 第一次写题解，有写的不好的地方可以私信我指出，谢谢。

2. 题目难度估计在 绿。

---

题目大意：

题意很好懂，看两个人谁第一次拿走某种颜色的球，输出比分。

---

题目思路：

我们可以把这个双端队列看作一个 长度为 $n$ 的区间，这个大区间可以划分成很多个 小区间。

---

首先：编号为 $a_i$ 的球在哪段区间拿会得到一分？

注：题目说了两端都能拿球。

其实很简单，我们假定一个区间 $[l,r]$，如果编号为 $a_i$ 的球第一次出现在 $2$ 号位，最后一次出现在 $10$ 号位，区间为 $[4,7]$，那么这个球早在 $4$ 号位的前面或者 $7$ 号位的后面拿过了。原因是区间最左边和最右边的外面就有 想要的球 了。

如果区间 $[l,r]$ 不能把编号为 $a_i$ 的球 第一次出现的位置 和 最后一次出现的位置 囊括。那么这一段区间一定不能得分。

这一步，我们只需要记录每种球 第一次出现的位置 和 最后一次出现的位置，判断区间 $[l,r]$ 是否囊括球的位置即可。

---

其次：怎样拿球双方都最优？

使用记忆化和 DP。

$dp_{l,r}$ 表示在区间 $[l,r]$ 内 自己得到的加分。

什么叫加分？

如果 $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}$ 的。

有些地方可能你没看懂，这里给上参考代码帮助你理解，代码也有注释。

---

参考代码：

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

---

总结：

一道不错的思维题，做法也很灵活，有不懂可以私信我，谢谢大家。