Levko and Array

题意：

有一长度为n的正整数序列，你可以选择K个数字任意改变它，使得$max \{ a(i+1) - a(i) \} $ 最小，求最小值。

解法：

1.$O(n^2log(MAX_A) )$，考虑二分出$d = max \{ a(i+1) - a(i) \} $，这样考虑dp

$f(i,j)$表示前i个数字，末位的数字为j的时候最少修改了多少数字

$f(i,j) = min \{ f(i-1,k) \} (j-d ≤ k ≤ j+d,j = a(i))$

$f(i,j) = min \{ f(i-1,k) \} (j-d ≤ k ≤ j+d,j ≠ a(i))$

注意到有效的j只有$a(i),a(i)-d,a(i)+d$，从而对第二维离散化，同时用单调队列维护区段min即可

（维护方法，对于 前面出现的 比后面的数字小 的数一定不会出现在答案中，这样只要维护一个单调增的双端队列即可）

此方法常数过大，TLE

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <ctime>

 #define LL long long

 #define N 2010

 #define INF 0x3f3f3f3f

 using namespace std;

 int n,m,K,minh,maxh,tots;

 int a[N],a0[N*];

 int f[N][N*],q[N*];

 double tott;

 int Abs(int x)

 {

     if(x<) return -x;

     return x;

 }

 bool check(int d)

 {

     a0[]=;

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

     {

         a0[++a0[]]=a[i];

         if(a[i]-(LL)d>=(LL)minh) a0[++a0[]]=a[i]-d;

         if(a[i]+(LL)d<=(LL)maxh) a0[++a0[]]=a[i]+d;

     }

     sort(a0+,a0+a0[]+);

     m=;

     for(int i=;i<=a0[];i++) if(a0[i]!=a0[i-]) a0[++m]=a0[i];

     for(int i=;i<=m;i++) f[][i]=;

     int t1=lower_bound(a0+,a0+m+,a[])-a0;

     f[][t1]=;

     int st=,ed=;

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

     {

         st=, ed=;

         int tmp=,minv=K+;

         for(int j=;j<=m;j++)

         {

             while(tmp<=m && a0[tmp]<=a0[j]+d)

             {

                 while(st<=ed && f[i-][q[ed]]>=f[i-][tmp]) ed--;

                 q[++ed]=tmp++;

             }

             while(st<ed && a0[q[st]]<a0[j]-d) st++;

             int k=q[st];

             if(a0[j]==a[i]) f[i][j]=f[i-][k];

             else f[i][j]=f[i-][k]+;

             minv = min(minv, f[i][j]);

             if(f[i][j] + n-i <= K) return ;

         }

         if(minv > K) return ;

     }

     return ;

 }

 int main()

 {

     freopen("test.txt","r",stdin);

     while(~scanf("%d%d",&n,&K))

     {

         unsigned int l=,r=;

         a0[]=;

         minh=INF;

         maxh=-INF;

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

         {

             scanf("%d",&a[i]);

             minh=min(minh,a[i]);

             maxh=max(maxh,a[i]);

             if(i>) r = max(r,(unsigned int)Abs(a[i]-a[i-]));

         }

         while(r-l>)

         {

             unsigned int mid=(l+r)>>;

             if(check(mid)) r=mid;

             else l=mid;

         }

         for(unsigned i=l;i<=r;i++)

             if(check(i))

             {

             //    cout << clock()/1000.0 << endl;

                 cout << i << endl;

                 break;

             }

     }

     return ;

 }

2.注意到方法一中第二维实际只有 j=a(i) 和其他的j ，两种j。

从而设$f(i)$表示前i个数字，数字i不改变 最少修改了多少数字。

这样有

$f(i) = min \{  f(j) + j-i-1 \}, ( \frac{|a(i)-a(j)|}{i-j} ≤ d )$

（i到j之间的数字全都改变）

小常数飘过

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <ctime>

 #define LL long long

 #define N 2010

 #define INF 0x3f3f3f3f

 using namespace std;

 int n,m,K,a[N];

 int f[N];

 LL Abs(LL x)

 {

     if(x<) return -x;

     return x;

 }

 bool check(int d)

 {

     f[]=;

     if(n-<=K) return ;

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

     {

         f[i]=i-;

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

             if(Abs(a[i]-(LL)a[j]) <= d*(LL)(i-j))

                 f[i] = min(f[i], f[j]+i-j-);

         if(f[i]+n-i<=K) return ;

     }

     return ;

 }

 int main()

 {

 //    freopen("test.txt","r",stdin);

     while(~scanf("%d%d",&n,&K))

     {

         LL l=,r=;

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

         {

             scanf("%d",&a[i]);

             if(i>) r = max(r,(LL)Abs(a[i]-a[i-]));

         }

         while(r-l>)

         {

             LL mid=(l+r)>>;

             if(check(mid)) r=mid;

             else l=mid;

         }

         for(unsigned i=l;i<=r;i++)

             if(check(i))

             {

                 cout << i << endl;

                 break;

             }

     }

     return ;

 }