2022 年杭电多校第六场 Multiply 2 Divide 2
题意：
BXY的序列\(a\)长度为\(n\) \((1\leq n\leq10^5,1\leq a_i\leq10^5)\)
对于每个操作，他选择一个数字\(a_i(1\leq i\leq n)\)并将其更改为\(a_i*2\)或\(\lfloor \frac{a_i}{2} \rfloor\)。BXY想知道将序列a更改为非下降序列的最少的操作数。
多测，数据最多五组
思路：
我们可以先考虑一个暴力出来。
设\(f_i,_j,_k\)表示第\(i\)个数字除了\(j\)次，乘了\(k\)次之后，让前面不递减的最小次数
我们可以得到以下转移：\(f_{i+1},_{j'},_{k'}=f_i,_j,_k+j'+k'\),当且仅当\(⌊ \frac{a _{i + 1}}{2^{j′}} ⌋ {2^{k ′}} ≥⌊ \frac{a _{i }}{2^{J}} ⌋ {2^{k }}\)
可能你会疑问，为什么满足此条件便成立呢？不用考虑乘除影响吗？
易知，先乘（全乘）再除是负收益。那么我们可不可以先除一些再乘一些再除一些呢？当然也是不可以的，因为乘完之后再除收益又变成负的了。为了保证所以值合理运用就只能先全除后乘了。(例如a*2/2=a,本来一次都不用的，你非要用两次)
再判断状态数量。设\(M\)为其中最大值。第一维\(O(n)\)，第二维\(O(logMlogM)\),第三位是\(O(30)\)（毕竟一个数的乘法次数不能超过30次，当然这只是预估，你可以开大一点，但是绝对不小于\(logM\)),时间复杂度无法接受，考虑优化
我们发现，这种序列会有两种可能的情况：
1.全部小于等于M
2.1-i都小于等于M，i+1-n大于M
那么，当这个\(a_{i+1}\)为那个第一个大于M的数时，它一定是除完后一直乘直到恰好大于M的第一个数
基于此，我们不妨设两个数组\(ga_i,_j,gb_i,_j\)。
\(ga_i,_j\)为第\(i\)个数先除\(j\)次后让其变成第一个大于M的数，且保证其后面的数单调递增的最小次数，\(gb_i,_j\)为辅助变量，表示为这个第一个大于M的数的值
例如，当M=7，x=4时，\(gb_1,_1=8,ga_1,_1=3\),因为\(4/2=2,2*2=4,4*2=8\)，三次
那么本题的答案便是这个序列两种情况的最小值，其实就做完了。
看到这你应该是蒙的，所以我们具体解释一下如何实现
先解决第一个问题：\(ga,gb\)的初始化。
先预处理出每个数除j次的值，且保证其从大到小
我们先处理出每个数本身，不考虑其他数。这时的\(ga_i,_j\)代表的是\(i\)这个数除j次之后使得其恰好大于\(M\)的最小次数 就拿样例来说，\(ga_1,_2=6,gb_1,_2=16\)
然后，倒序递推即可
for(int k=0;k<20&&gb[i+1][k];k++){
if(gb[i+1][k]<gb[i][j])mx=min(mx,ga[i+1][k]+n-i);//后面比前面小 全体乘2保证单调性
else mx=min(mx,ga[i+1][k]);
}
ga[i][j]+=mx;
处理第二个问题：两个序列如何求最小值？
对于第一种情况：
flag=INF;
for(int j=0;j<g[i].size();j++){
while(k<g[i-1].size()&&g[i-1][k].val<=g[i][j].val){//如果前面小于后面
flag=min(flag,g[i-1][k].times);//在j不动的情况下求一个最小值
k++;
}
g[i][j].times+=flag;
}
对于第二种情况：
while(k<g[i-1].size()&&g[i-1][k].val<=mx){//钦定第i(i>1)个数为那个第一个大于M的数
flag=min(flag,g[i-1][k].times);//所以前面只要小于M都可以，无所谓
k++;
} for(int j=0;j<20&&gb[i][j];j++)ans=min(ans,ga[i][j]+flag);//前面的最小+预处理数组ga
所以这道题就做完了
完整代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
const int INF=2e17;
struct node{
int val,times;
};
int t,n,mx;
int val[maxn];
int ga[maxn][20],gb[maxn][20];
vector<node>g[maxn];
signed main(){
cin>>t;
while(t--){
scanf("%lld",&n);mx=-1;
for(int i=1;i<=n;i++){
g[i].clear();
for(int j=0;j<20;j++){
ga[i][j]=INF;
gb[i][j]=0;
}
}
for(int i=1;i<=n;i++)scanf("%lld",&val[i]),mx=max(mx,val[i]);//M的预处理
for(int i=1;i<=n;i++){
vector<int>d;
d.clear();
d.push_back(val[i]);
while(d.back()>1)d.push_back(d.back()/2);//倒叙添加
int cnt=d.size();
g[i].push_back((node){0,cnt});//当然可以除成0
for(int j=cnt-1;d.back()<=mx;j--){//j可以小于0
for(int k=cnt-1;k>=max(j,(int)0);k--){
//这里的g其实只求了它本身除j次后变成>M的最小次数
if(d[k]<=mx){
g[i].push_back((node){d[k],2*k-j});//存下那些小于M的数为第一种序列做准备
d[k]=d[k]*2;
}
if(d[k]>mx&&(!gb[i][k])){
gb[i][k]=d[k];
ga[i][k]=2*k-j+1;//最后一次需要单独计算,于是+1
}
}
}
}
//g的前缀和求法
for(int i=n-1;i>=1;i--){
for(int j=0;j<20&&gb[i][j];j++){
mx=INF;
for(int k=0;k<20&&gb[i+1][k];k++){//前提是这个数除以k次后不为0
if(gb[i+1][k]<gb[i][j])mx=min(mx,ga[i+1][k]+n-i);//后面比前面小 全体乘2保证单调性
else mx=min(mx,ga[i+1][k]);
}
ga[i][j]+=mx;
}
}
int ans=INF;
for(int i=2;i<=n;i++){
int k=0,flag=INF;
for(int j=0;j<g[i].size();j++){
while(k<g[i-1].size()&&g[i-1][k].val<=g[i][j].val){//如果前面小于后面
flag=min(flag,g[i-1][k].times);//在j不动的情况下求一个最小值
k++;
}
g[i][j].times+=flag;
}
while(k<g[i-1].size()&&g[i-1][k].val<=mx){//钦定第i个数为那个第一个大于M的数
flag=min(flag,g[i-1][k].times);//所以前面只要小于M都可以，无所谓
k++;
}
for(int j=0;j<20&&gb[i][j];j++)ans=min(ans,ga[i][j]+flag);//前面的最小+预处理数组ga
}
for(int i=0;i<g[n].size();i++){
ans=min(ans,g[n][i].times);//对第一种序列的整体求最小
}
printf("%lld\n",ans);
}
return 0;
}
后记
DP暴力优化是一种常用的手段，除了四边形，斜率等之类的优化，我们还可以对于转移加上限制（当然这道题没有使用）以达到我们的目的或寻找序列性质，用辅助数组加速优化。
其实我感觉这道题有点根号分治那味