题解：P9911 [COCI 2023/2024 #2] Kuglice

· · 题解

题目传送门

题目大意

有一个双端队列，你可以在队列头尾拿一个数，如果这个数是第一次拿出来就加一分，最后比分数多少（题意还是很好理解的）。

思路

首先分析大致复杂度

看数据范围 n=3000 这样的话 O(n^{2}) 的复杂度就可以跑过。

接着找最优策略

很明显总分是一定的，那么我的得分每一次高，最后一定高。

然后算法分析

我们把这一个队列看成一个从 l\sim r 的区间，我们每一次取的时候可以让这个区间变成 l+1\sim r 或者是 l\sim r-1 那么我们只需要查看一下这两个区间哪一个更优就选哪一个，相信到这里大家可以看出这就是个记搜。

最后具体实现

我们想当总分为 k 然后我比对手高 h 分时 （这个 h 可能为负），我的分数是多少？肯定就是 \frac{k+a}{2} 这不就出来了吗！

把这个代入到这道题中我们先记录一下有 k 种不同的数字，以及当前我比对手大的分数 dp_{1,n} 这样易得出的 \frac{k+dp_{1,n}}{2} 是我分数，紧接着就是如何求 dp 呢？

这个 dp 的思路其实就是我前面说的在两个区间之中取最大值，但是直接搜索会超时，优化就是我们在这个 dp 之中如果已经有数了，就不用接着搜下去直接返回这里面的值。

方程转移式最后就是：

dp[l][r]=max(win(l,r,a[l])-dfs(l+1,r),win(l,r,a[r])-dfs(l,r-1));

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int n,much,maxa;
int a[N],head[N],tail[N],tong[N],dp[N][N];
int win(int l,int r,int val){//判断这个数是否是第一次出现，是的话返回一否则是零 
    if(head[val]>=l&&tail[val]<=r) return 1;
    else return 0;
}
int dfs(int l,int r){//记搜找最优方案 
    if(l==r) return win(l,r,a[l]); //如果区间只剩一个数，那么直接看这个数满不满足 
    if(dp[l][r]!=-1) return dp[l][r];//如果已有记录，就直接返回 
    dp[l][r]=max(-dfs(l+1,r)+win(l,r,a[l]),-dfs(l,r-1)+win(l,r,a[r]));//状态转移 
    return dp[l][r];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];//读入 
    for(int i=1;i<=n;i++){//从前向后看每一个数，第一次出现的位置 
        if(!tong[a[i]]) head[a[i]]=i;
        tong[a[i]]=1;
    }
    memset(tong,0,sizeof(tong));
    for(int i=n;i>=1;i--){//从后向前看每一个数，第一次出现的位置 
        if(!tong[a[i]]) tail[a[i]]=i,much++;
        tong[a[i]]=1;
    }
    memset(dp,-1,sizeof(dp));//先给出初值 
    maxa=dfs(1,n);
    cout<<(much+maxa)/2<<":"<<(much-maxa)/2;//算出我的和对方的分数 
    return 0;
}//完美收官