[USACO08FEB]修路Making the Grade

[USACO08FEB]修路Making the Grade
比较难的dp，比赛时打的找LIS，然后其他的尽可能靠近，40分。
先举个例子
6
1 2 3 1 4 5
6
1 2 3 3 4 5
第4个1要么改成3，要么改成4，反正是数列中的数。
所以最优情况下，答案中的数都是原数列中有的。
b[]是a[]由小到大排序之后的数组
令f[i][j]表示使前i个数成为不减的最小花费，而且第i个的高度为b[j].
f[i][j]=min(f[i-1][k])+abs(a[i]-b[j]);1<=k<=n
k从1~n递增，一个显然的优化就是单调队列，递增的，每次取队首。
不增同理。

AC：

#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cmath>

#include<ctime>

#include<cstring>

#define inf 2147483647

#define For(i,a,b) for(register int i=a;i<=b;i++)

#define p(a) putchar(a)

#define g() getchar()

//by war

//2017.10.18

using namespace std;

int f[][];

int q[];

int a[];

int b[];

int l,r;

int ans;

int n;

int m;

void in(int &x)

{

    int y=;

    char c=g();x=;

    while(c<''||c>'')

    {

    if(c=='-')

    y=-;

    c=g();

    }

    while(c<=''&&c>='')x=x*+c-'',c=g();

    x*=y;

}

void o(int x)

{

    if(x<)

    {

        p('-');

        x=-x;

    }

    if(x>)o(x/);

    p(x%+'');

}

int main()

{

    in(n);

    For(i,,n)

    in(a[i]),b[i]=a[i];

    sort(b+,b+n+);

    m=unique(b+,b+n+)-b-;

    For(i,,n)

      {

          r=;

          For(j,,m)

        {

            while(r&&f[i-][j]<=f[i-][q[r]])r--;

            q[++r]=j;

            f[i][j]=f[i-][q[]]+abs(a[i]-b[j]);

        }

      }

    ans=inf;

    For(i,,m)

    ans=min(ans,f[n][i]);

    For(i,,n)

      For(j,,n)

        f[i][j]=;

    For(i,,n)

      {

          r=;

          For(j,,m)

        {

            while(l<=r&&f[i-][j]>=f[i-][q[r]])r--;

            q[++r]=j;

            f[i][j]=f[i-][q[]]+abs(a[i]-b[m]);

        }

      }

    ans=min(ans,f[n][m]);

    o(ans);

     return ;

}

考场贪心骗分代码：

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<cstring>

 #define inf 2147483647

 #define For(i,a,b) for(register int i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.10.18

 using namespace std;

 int n;

 int Max;

 int last;

 int a[];

 int d[];

 bool b[];

 int p[];

 int f[];

 int ans[];

 void in(int &x)

 {

     int y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=x*+c-'',c=g();

     x*=y;

 }

 void o(int x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 void LIS()

 {

     For(i,,n)

     f[i]=,d[i]=;

     For(i,,n)

       {

           For(j,,i-)

         {

             if(a[j]<=a[i])

             {

                 if(f[j]+>f[i])

                 {

                     f[i]=f[j]+;

                     d[i]=j;

                 }

             }

         }

         if(Max<f[i])

         {

             Max=f[i];

             last=i;

         }

       }

       int ft;

       for(ft=last;d[ft]!=;ft=d[ft])

       b[ft]=true;

       for(int i=ft-;i>=;i--)

       {

           ans[]+=abs(p[i]-p[i+]);

           p[i]=p[i+];

       }

       For(i,ft+,n)

       if(!b[i])

       {

           ans[]+=abs(p[i]-p[i-]);

           p[i]=p[i-];

       }

 }

 void LRS()

 {

     Max=;

     For(i,,n)

     f[i]=,b[i]=false,d[i]=;

     For(i,,n)

       {

           For(j,,i-)

         {

             if(a[j]>=a[i])

             {

                 if(f[j]+>f[i])

                 {

                     f[i]=f[j]+;

                     d[i]=j;

                 }

             }

         }

         if(Max<f[i])

         {

             Max=f[i];

             last=i;

         }

       }

       int ft;

       for(ft=last;d[ft]!=;ft=d[ft])

       b[ft]=true;

       for(int i=ft-;i>=;i--)

       {

           ans[]+=abs(p[i]-p[i+]);

           p[i]=p[i+];

       }

       For(i,ft+,n)

       if(!b[i])

       {

           ans[]+=abs(p[i]-p[i-]);

           p[i]=p[i-];

       }

 }

 int main()

 {

 //    freopen("grading.in","r",stdin);

 //    freopen("grading.out","w",stdout);

     in(n);

     For(i,,n)

     in(a[i]),p[i]=a[i];

     LIS();

     For(i,,n)

     p[i]=a[i];

     LRS();

     o(min(ans[],ans[]));

      return ;

 }