P9317 [EGOI2022] SubsetMex / 子集 mex

qwerty12346 · 2023-06-07 16:50:07 · 题解

题目传送门

题意

这题就是求最少的操作次数。

思路

直接 for 循环求操作次数。我们再做个函数求操作次数。最后我们只需要算其中 n 个数就可以了。我们会发现选出一个超过 i 的数，他对于使得 \operatorname{mex}(S) 等于 i 没有贡献，那么这就是一个无后效性子问题 Q(i)。

注意要将 dp_{i,j} 的初始值定为 1。我这里是算完操作次数后加的 1。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,x,a[10005];
long long f(long long i,long long j){//求操作次数的函数
   if(!i)return 0;//特判
   return a[i]>=j?f(i-1,j):f(i-1,j+j-a[i])+j-a[i];//计算其中n的个数
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {   
        cin>>x;
    for(int j=1;j<=x;j++)cin>>a[j];
    cout<<f(x,1)+1<<endl;//算完加一
    }
    return 0;
}