hdu 3666 Making the Grade

题目大意

给出了一列数，要求通过修改某些值，使得最终这列数变成有序的序列，非增或者非减的，求最小的修改量。

分析

首先我们会发现，最终修改后，或者和前一个数字一样，或者和后一个数字一样，这样才能修改量最小。

我们先根据原数列排序，确定元素的大小关系，对应编号为p[i]

dp[i][j] 表示考虑前i个元素，最后元素为序列中第j小元素的最优解

dp[i][j] = MIN(dp[i-1][k]) + abs(a[i]-a[p[j]]), (0<k<=j)

刚开始以为是o(n^3）的复杂度，后来想想，k值在每次j循环的时候就能确定最小值

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define INF 100000000000000

 #define maxn 2005

 using namespace std;

 int n;

 typedef long long LL;

 LL a[maxn],b[maxn];

 LL dp[maxn][maxn];

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

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

         {

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

             b[i]=a[i];

         }

         sort(b+,b++n);

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

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

                 dp[i][j]=INF;

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

         {

             dp[][j]=(a[]-b[j]);

             if(dp[][j]<)

                 dp[][j]=-dp[][j];

         }

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

         {

             LL k=dp[i-][];

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

             {

                 k=min(dp[i-][j],k);

                 LL tem=(a[i]-b[j]);

                 if(tem<)

                     tem=-tem;

                 dp[i][j]=min(dp[i][j],k+tem);

                 // printf("==%I64d\n",dp[i][j]);

             }

         }

         LL minn=INF;

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

             minn=min(minn,dp[n][i]);

         printf("%I64d\n",minn);

     }

     return ;

 }

巴特西

hdu 3666 Making the Grade

最新文章

热门文章