Codeforces 13C(DP)

题意：给出一个数列长度小于5000，每次操作将数列中的数加1或减1，问最少需要多少步操作可以得到一个不降序列；

分析：可知最少的次数，一定是由原来的数据构成的（据说可以用反证法证），即有原来的数组成的不降子序列中有一个最小的情况；

我们用F[i][j] = min(F[i][j -1] （不包含这一个时）,F[i-1][j] + fabs(A[i] - B[j])（包含这一种时）);其中B[]代表不重非减序列i,j代表前个数最大为B[j]时的最优情况；

注意：本题数据大，F[][]的过程用到了滚动数组；

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 int A[],B[],C[];

 __int64 F[][];

 __int64 min(__int64 a,__int64 b)

 {

     return a > b ? b:a;

 }

 int cmp(const void *a,const void *b)

 {

     return *(int *)a - *(int *)b;

 }

 int main()

 {

     int n,m,i,j,a,b;

     scanf("%d",&n);

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

     {

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

         C[i] = A[i];

     }

     qsort(C + , n, sizeof(C[]), cmp);

     B[] = C[];

     m = ;

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

     if(C[i] > B[m])

     {

         ++ m;

         B[m] = C[i];

     }

     F[][] = fabs(A[] - B[]);

     for(i = ;i <= m;i ++)

         F[][i] = min(F[][i -],fabs(A[] - B[i]));

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

         {

             F[i&][] = F[ - (i&)][] + fabs(A[i] - B[]);

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

         F[i&][j] = min(F[i&][j - ],F[ - i&][j] + fabs(A[i] - B[j]));

         }

     printf("%I64d",F[n&][m]);

     return  ;

 }