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

总结：

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[3010],dp[3010][3010];
struct N{
	int l,r;
}f[3010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int s=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(!f[a[i]].l)f[a[i]].l=i,s++;
		f[a[i]].r=i;
	}
	for(int i=1;i<=n;i++){
		if(f[a[i]].l==f[a[i]].r)dp[i][i]=1;
	}
	for(int l=2;l<=n;l++){
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			if((n-l)&1){
				dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
			}
			else{
				dp[i][j]=max(dp[i+1][j]+(f[a[i]].l>=i&&f[a[i]].r<=j),dp[i][j-1]+(f[a[j]].l>=i&&f[a[j]].r<=j));
			}
		} 
	}
	cout<<dp[1][n]<<":"<<s-dp[1][n];
	return 0;
}

这题数据估计很水：

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int dp[N][N],L[N],R[N],a[N],v[N];
bool check(int l,int r,int x){return L[x]>=l&&R[x]<=r;}
signed main()
{
	int n,cnt=0;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(!v[a[i]])
		{
			cnt++;
			L[a[i]]=i;
			v[a[i]]=1;
		}
		R[a[i]]=i;
	}
	for(int i=1;i<=n;i++)dp[i][i]=check(i,i,a[i]);
	for(int k=1;k<=n;k++)for(int l=1;l+k<=n;l++)
	{
		int r=l+k;
		dp[l][r]=max(check(l,r,a[l])-dp[l+1][r],check(l,r,a[r])-dp[l][r-1]);
	}
	int ans=(cnt+dp[1][n])/2;
	cout<<ans<<":"<<(cnt-ans)<<'\n';
	return 0;
}