You Are the One

题意：

有n个人排队，第i个入场的人x的不愉快度是$D_x*(i-1)$，现在给你n个人在队伍中的位置，

你可以用一个栈让一个人后面的人先进入，问最小的不愉快度是多少。

解法：

考虑注意到用栈调整次序时，如果$x_1$从$l$调整到了$r$的位置，那么如果有$x_2$的位置在$l$，

$r$之间那么一定要满足$l<l_2<=r_2<r$。

这样考虑dp：

$f(i,j)$表示i到j最大可以通过调整减小多少的不愉快度，这样就可以dp了。

（注意在转移不交换的情况下$f(i,j) = max \{ f(i+1,j), f(i,j-1) \}$ 不正确，

因为这样求出来的是一个一个大区间套着小区间的答案，不能表示两个区间相互独立的情况，

应该是$f(i,j) = max \{ f(i,k)+f(k+1,j) \}$）

时间复杂度$O(n^3)$。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define N 110

 using namespace std;

 int n,ans;

 int D[N],f[N][N],S[N];

 int main()

 {

     int T,Te=;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         S[]=;

         ans=;

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

         {

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

             S[i]=S[i-]+D[i];

             ans+=(i-)*D[i];

         }

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

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

         {

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

             {

                 int j=i+d-;

                 f[i][j]=;

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

                     f[i][j] = max(f[i][j], f[i][k]+f[k+][j]);

                 f[i][j] = max(f[i][j], f[i+][j]+S[j]-S[i]-D[i]*(j-i));

             }

         }

         printf("Case #%d: %d\n",++Te,ans-f[][n]);

     }

     return ;

 }

巴特西

You Are the One

最新文章

热门文章