题目

https://mp.weixin.qq.com/s/ig1RZFgLeGlON0vsh4rIFg

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2E4+10;
int n, a[N];
unordered_map<int, int> f[N];  //f[i][j]表示前i个元素都已经变成非递减数组，并且第i个元素修改成j的最小操作数
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    f[0][1] = 0;               //因为最小数为1，所以第0个数变成1的最小操作数为0
    for(int i=1; i<=n; i++){
        for(int cnt=0, j=a[i]; j>=1; j>>=1, cnt++){
            for(auto &[u, v]:f[i-1]){                               //这里的u相当于f[i][j]的j,v相当于f[i][j]的值
                if(u<=j){
                    if(!f[i].count(j)) f[i][j] = f[i-1][u]+cnt;     //如果之前状态f[i][j]不存在就创建一个
                    else f[i][j] = min(f[i][j], f[i-1][u]+cnt);     //只要u小于a[i]/(2^cnt)，那么a[i]就可以经过cnt次除以2的操作实现前i个数的非递减数组
                }
            }
        }
        for(int cnt=0, j=a[i]; j<N; j<<=1, cnt++){
            for(auto &[u, v] : f[i-1]){
                if(u<=j){
                    if(!f[i].count(j)) f[i][j] = f[i-1][u]+cnt;
                    else f[i][j] = min(f[i][j], f[i-1][u]+cnt);
                }
            }
        }
    }
    int res = 1e9;
    for(auto &[u, v]:f[n]) res = min(res, v);
    printf("%d", res);
}