[COCI 2023-2024 #2] Kuglice 解题记录
题意简述
一个长度为 n n n 的序列中有 n n n 个球，每个球有一个颜色。现在 A 和 B 轮流从两端取球，如果取的球的颜色之前没有取过就得一分，输出最终比分。
题目分析
因为这个序列是不断缩小的，且两端都可以删除，所以可以看成一个区间，考虑使用区间 DP。
如何设状态？
既然是区间 DP，那么状态肯定是 d p l , r dp_{l,r} dpl,r，表示当前取的人比另外一个多得的分数。设颜色总数为 s s s，那么这个人的得分就是 s + d p 1 , n 2 \frac{s+dp_1,n}{2} 2s+dp1,n。
如何转移？
观察数据范围 1 ≤ n ≤ 3000 1 \leq n \leq 3000 1≤n≤3000，可以支持 O ( n 2 ) O(n^2) O(n2) 的算法，考虑记忆化搜索。我们暴力地去枚举当前这个人是从前面取还是从后面取，对求出来的值取最大值即可。如果 B 比 A 多 k k k 分，A 就比 B 多 − k -k −k分，那么如果 A 取的这个球可以得分，那么 A 就比 B 多 − k + 1 -k+1 −k+1 分；反之亦然。
如何判断这个球是否可以得分？
用数组记录每种颜色的球的第一次出现的位置 i d l , i d r idl,idr idl,idr（从左到右和从右到左），设当前取的球的区间在 [ l , r ] [l,r] [l,r]，如果 i d l a l ≤ [ l , r ] ≤ i d r a r idl_{a_l} \leq [l,r] \leq idr_{a_r} idlal≤[l,r]≤idrar 那么就得不到分，因为之前已经取过了；反之亦然。
设当前的得分为 k ∈ [ 0 , 1 ] k \in [0,1] k∈[0,1]，状态转移方程：
d p l , r = max ( k − d p l + 1 , r , k − d p l , r − 1 ) dp_{l,r}=\max(k-dp_{l+1,r},k-dp_{l,r-1}) dpl,r=max(k−dpl+1,r,k−dpl,r−1)
最后的答案是 s + d p 1 , n 2 : s − d p 1 , n 2 \frac{s+dp_{1,n}}{2} : \frac{s-dp_{1,n}}{2} 2s+dp1,n:2s−dp1,n。
AC Code
#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)std::cin>>a[i]
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N=3005;
int n,sum,cnt1,cnt2,a[N],idxl[N],idxr[N],dp[N][N];
int dfs(int l,int r){
if(l>r){
return 0;
}
if(dp[l][r]==-1){
dp[l][r]=std::max((l<=idxl[a[l]]&&r>=idxr[a[l]])-dfs(l+1,r),(l<=idxl[a[r]]&&r>=idxr[a[r]])-dfs(l,r-1));
}
return dp[l][r];
}
signed main() {
mem(dp,-1);
std::cin>>n;
arrin(a,n);
rep(i,1,n){
if(!idxl[a[i]]){
sum++;
idxl[a[i]]=i;
}
}
dep(i,n,1){
if(!idxr[a[i]]){
idxr[a[i]]=i;
}
}
std::cout<<(sum+dfs(1,n))/2<<":"<<(sum-dfs(1,n))/2;
return 0;
}