BZOJ 1049 数字序列

2022-10-11 16:47:40

Description

现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

Input

第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。

Output

第一行一个整数表示最少需要改变多少个数。第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

Sample Input

4
5 2 3 5

Sample Output

1
4

HINT

【数据范围】

90%的数据n<=6000。

100%的数据n<=35000。

保证所有数列是随机的。

Source

这道题感觉太神了。

令原数组为a。

对于第一问我们可以反过来思考——要求最少的改动的，不就是求最多的不改动的吗？

f[i]表示前i位最多的不改动的数字个数，f[i]=max(f[j]+1)，j需要满足a[i]-a[j]≥i-j。对于条件，我们移一下项，化为a[i]-i≥a[j]-j，令b[i]=a[i]-i，不就是b[i]≥b[j]。细心的朋友一定看出来了，这不就是最长不下降子序列吗！！！O(nlogn)的求法上起。

第二问稍微麻烦一点，我们要知道一个结论：另g[i]表示前i个数，在改动数最少的前提下，最少改动的值。

那么对于所有合法的转移i，j(i>j，f[i]=f[j]+1，b[i]≥b[j])，最优解一定是在i与j之间某个k，k到j的值全为b[j]，k+1到i的值全为b[i]。因此就可以dp了。证明自己脑补一下就可以了。。。(自己画画图，根据条件想想应该是可以明白的)

 #include<cstring>

 #include<vector>

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 #define inf (1<<30)

 #define maxn 35010

 int tree[maxn],tot,n,f[maxn],a[maxn],bac[maxn];

 long long g[maxn],s1[maxn],s2[maxn];

 vector <int> vec[maxn];

 inline int lowbit(int x) { return x & -x; }

 inline void change(int a,int b) { for (;a <= tot;a += lowbit(a)) tree[a] = max(tree[a],b); }

 inline int calc(int a) { int ret = ; for (;a;a -= lowbit(a)) ret = max(ret,tree[a]); return ret; }

 int main()

 {

     freopen("1049.in","r",stdin);

     freopen("1049.out","w",stdout);

     scanf("%d",&n);

     for (int i = ;i <= n;++i) scanf("%d",a+i),a[i] -= i,bac[++tot] = a[i];

     a[++n] = inf; bac[++tot] = a[n];

     sort(bac+,bac+tot+); tot = unique(bac+,bac+tot+) - bac - ;

     for (int i = ;i <= n;++i)

     {

         int pos = lower_bound(bac+,bac+tot+,a[i]) - bac;

         f[i] = calc(pos) + ;

         change(pos,f[i]);

     }

     printf("%d\n",n-f[n]);

     for (int i = ;i <= n;++i) vec[f[i]].push_back(i);

     a[] = -inf;

     memset(g,0x7,sizeof(g)); g[] = ;

     for (int i = ;i <= n;++i)

     {

         int nn = vec[f[i] - ].size();

         for (int p = ;p < nn;++p)

         {

             int j = vec[f[i]-][p];

             if (j >= i) break; if (a[i] < a[j]) continue;

             for (int k = j;k <= i;++k) s1[k]=abs(a[k]-a[j]),s2[k]=abs(a[k]-a[i]);

             for (int k = j+;k <= i;++k) s1[k] += s1[k-],s2[k] += s2[k-];

             for (int k = j;k < i;++k) g[i] = min(g[i],g[j]+s1[k]-s1[j]+s2[i]-s2[k]);

         }

     }

     printf("%lld",g[n]);

     fclose(stdin); fclose(stdout);

     return ;

 }

码农公寓