题解：AT_abc443_d [ABC443D] Pawn Line / [SNOW] - 21

· · 题解

这题挂了 2 发，不像是人了。

题意转化：

给你一个数列，定义一次操作为选择一个数字将其减一，你需要求出使序列相邻位差值不大于 1 的最小操作次数。

难点在于读题，一旦看出来这题是上面这样那就是一眼的吧。

容易发现一定是用小的数字去影响大的数字，根据转移关系容易建出一张 DAG，这时显然可以跑 DAG DP。

这张图的拓扑序显然是按照元素大小升序排序后的结果。

暴力转移的话就是对于每个点向两端进行扩展，算对应大小并进行转移。

不过这个做法很有问题，时间复杂度 O(n^2) 显然会爆炸。

但是有一个显然的剪枝，如果遇到无法转移的点，此时让这个点接着往下去转移显然更加优秀，于是这个点的转移就可以提前退出了。

观察这样剪枝后的时间复杂度，容易发现只考虑一边的扩展时间复杂度是线性的（类似于一个区间平推过去），扩展到两个方向就是带个常数。

于是时间复杂度 O(n\log n)，瓶颈在于排序。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define mod 998244353
#define int long long
using namespace std;
int ans[300005];
struct fish{
    int x,id;
}a[300005];
bool cmp(fish x,fish y){
    return x.x<y.x;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].x,a[i].id=i,ans[i]=a[i].x;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        for(int j=a[i].id+1;j<=n;j++){
            int x=j-a[i].id;
            x=a[i].x+x;
            if(ans[j]<=x)break;
            ans[j]=x;
        }
        for(int j=a[i].id-1;j;j--){
            int x=a[i].id-j;
            x=a[i].x+x;
            if(ans[j]<=x)break;
            ans[j]=x;
        }
    }
    int ret=0;
    for(int i=1;i<=n;i++)
    ret+=a[i].x-ans[i];
    cout<<ret<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}
//「所以，你刚才想做什么？」

// 我拋出这个话题，她立刻一惊，抓住深深盖住脸的兜帽帽檐，把头垂得更低。
//「……那个，拜托你。刚才的事不要跟别人说。」

//「我不是为了威胁你才问这个问题的，纯粹是因为好奇。我们前天好像在面包店碰过面对不对？那时你的样子也有点奇怪，让我有点在意。」