// 题目链接: https://nanti.jisuanke.com/t/28204
1 //动态规划，重复利用子问题的最优，来求解当前最优问题

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <vector>

 #include <queue>

 using namespace std;

 typedef long long ll;

 int  t;

 const int  N=;

 int s[N];

 int dp[N];//在第i层下楼时从一楼到i楼共生气的最小值

 const int inf=0x3f3f3f3f;

 int  main()

 {

     scanf("%d",&t);

     while(t--)

     {

         int  n;

         scanf("%d",&n);

         int  sum=;

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

       {

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

           sum+=s[i];

       }

       dp[]=;

       int ski;

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

       {

           sum-=s[i];//这一层下楼，那么此时前面的都会下，sum为高层人数。

           ski=;

           dp[i]=inf;

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

           {

                dp[i]=min(dp[i],dp[j]+ski+sum);//

                ski+=(i-j)*s[j];//该在j层下，却在i 层才下楼

           }

       }

       //因为dp[i]为i层下楼的。。，因此用不下楼来更新

       printf("%d\n",dp[n]);

     }

     return  ;

 }

  D. Lift Problems
 //在喜欢的里面取mid个，在不喜欢的里面取s-mid个。

  #include <iostream>

  #include <cstdio>

  #include <cstring>

  #include <algorithm>

  using namespace std;

  int T;

  const int N=1e5+;

  int t[N],p[N];

 int main()

 {

     int i,j,l,r,mid,maxx,n,s,f,k;

     scanf("%d",&T);

     while(T--)

     {

     scanf("%d%d%d",&n,&s,&f);

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

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

     sort(t,t+f);//要分别排序

     //因为分成喜欢与不喜欢

     sort(t+f,t+n);

     scanf("%d",&k);

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

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

     l=max(,s-(n-f));//下界

     r=min(s,f);//上界

     while(l<=r)//因为上界可能取到

    {

        mid=(l+r)>>;

        maxx=t[n-(s-mid)-];//不喜欢的不取的最大值

        for(i=;i<k-f-(s-mid);i++)//把P数组小的加到不喜欢的不取的小的部分

            maxx=max(maxx,p[i]+t[k--(s-mid)-i]);

        for(j=;j<mid&&t[f--j]+(k-mid+j<?:p[k-mid+j])>=maxx;j++);

        //喜欢中所取的所有值都要大于不喜欢中不取的最大值

        if(j==mid)//这个mid是可以的

            l=mid+;

        else

            r=mid-;

    }

    printf("%d\n",l-);

     }

     return    ;

 }