记录编号	616315	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]数字序列	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2026-06-12 11:51:25	内存使用	4.61 MiB

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define int long long
const int N = 3.5 * 1e4 + 5;
int n;
int a[N], b[N];
int f[N], now = 0;
int len[N], dp[N];
vector<int> G[N];
int s1[N], s2[N];

signed main(){

    cin >> n;

    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        b[i] = a[i] - i;
    }
    
    b[0] = -1e9;
    for(int i = 1;i <= n;i ++){
        f[i] = 1e9;
        dp[i] = 1e18;
    }
    f[0] = b[0];
    len[0] = 0;
    G[0].push_back(0);
    now = 0;
    b[n + 1] = 2e9;
    for(int i = 1;i <= n + 1;i ++){
        if(b[i] >= f[now]){
            f[++ now] = b[i];
            G[now].push_back(i);
            len[i] = now;
        }
        else{
            int pos = upper_bound(f + 1, f + now + 1, b[i]) - f;
            f[pos] = b[i];
            G[pos].push_back(i);
            len[i] = pos;
        }
    }
    cout << n - (now - 1) << '\n';
    
    dp[0] = 0;
    dp[n + 1] = 1e18;
    for(int j = 1;j <= n + 1;j ++){
        for(int o = 0;o < (int)G[len[j] - 1].size();o ++){
            int i = G[len[j] - 1][o];
            if(i > j || b[i] > b[j]) continue;
            s1[i] = 0;
            for(int k = i + 1;k < j;k ++){
                int val = b[k] - b[i];
                s1[k] = s1[k - 1] + (val > 0 ? val : -val);
            }
            // s2[i] = 0;
            // for(int k = i + 1;k < j;k ++){
            //     int val = b[k] - b[j];
            //     s2[k] = s2[k - 1] + (val > 0 ? val : -val);
            // }
            s2[j] = 0;
            for(int k = j - 1;k > i;k --){
                int val = b[k] - b[j];
                s2[k] = s2[k + 1] + (val > 0 ? val : -val);
            }
            int minx = 1e18;
            for(int k = i;k < j;k ++){
                minx = min(minx, s1[k] + s2[k + 1]);
            } 
            dp[j] = min(dp[j], dp[i] + minx);
        }
    }

    cout << dp[n + 1] << '\n';
    return 0;
}