[COCI 2023-2024 #2] Kuglice 解题记录

本文主要是介绍[COCI 2023-2024 #2] Kuglice 解题记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[COCI 2023-2024 #2] Kuglice 解题记录

题意简述

一个长度为 $n$ 的序列中有 $n$ 个球，每个球有一个颜色。现在 A 和 B 轮流从两端取球，如果取的球的颜色之前没有取过就得一分，输出最终比分。

题目分析

因为这个序列是不断缩小的，且两端都可以删除，所以可以看成一个区间，考虑使用区间 DP。
如何设状态？
既然是区间 DP，那么状态肯定是 $dp_{l,r}$ ，表示当前取的人比另外一个多得的分数。设颜色总数为 $s$ ，那么这个人的得分就是 $\frac{s+dp_1,n}{2}$ 。
如何转移？
观察数据范围 $\leq n \leq 3000$ ，可以支持 $O(n^2)$ 的算法，考虑记忆化搜索。我们暴力地去枚举当前这个人是从前面取还是从后面取，对求出来的值取最大值即可。如果 B 比 A 多 $k$ 分，A 就比 B 多 $- k$ 分，那么如果 A 取的这个球可以得分，那么 A 就比 B 多 $- k + 1$ 分；反之亦然。
如何判断这个球是否可以得分？
用数组记录每种颜色的球的第一次出现的位置 $i d l, i d r$ （从左到右和从右到左），设当前取的球的区间在 $[l, r]$ ，如果 $idl_{a_l} \leq [l,r] \leq idr_{a_r}$ 那么就得不到分，因为之前已经取过了；反之亦然。
设当前的得分为 $\in [0,1]$ ，状态转移方程：
$dp_{l,r}=\max(k-dp_{l+1,r},k-dp_{l,r-1})$
最后的答案是 $\frac{s+dp_{1,n}}{2} : \frac{s-dp_{1,n}}{2}$ 。

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