自动搬运

查看原文

来自洛谷，原作者为

	qwerty12346 这个家伙很懒，什么也没有留下(互关)

搬运于2025-08-24 22:47:17，当前版本为作者最后更新于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;
}