codeforces 355C - Vasya and Robot

因为在允许的情况下，必然是左右手交替进行，这样不会增加多余的无谓的能量。

然后根据不同的分界点，肯定会产生左手或右手重复使用的情况，这是就要加上Qr/Ql * 次数。

一开始的想法，很直接，枚举每个分界点，计算出总共要用的能量，取最小的那个即是答案：

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int main()

 {

     int n,l,r,Q_l,Q_r,w[+];

     scanf("%d%d%d%d%d",&n,&l,&r,&Q_l,&Q_r);

     for(int i=;i<=n;i++) scanf("%d",&w[i]);

     int ans=,left_enegry_sum,right_enegry_sum;

     for(int m=;m<=n;m++) //边界在m右边

     {

         left_enegry_sum=,right_enegry_sum=;

         for(int i=;i<=m;i++) left_enegry_sum+=w[i]*l;

         for(int i=n;i>m;i--) right_enegry_sum+=w[i]*r;

         if(m < n-m) //右手拿的东西多

             right_enegry_sum += ( (n-m) - m -  ) * Q_r;

         else if(m > n-m) //左手拿的东西多

             left_enegry_sum += ( m - (n-m) -  ) * Q_l;

         ans=min(ans , left_enegry_sum + right_enegry_sum);

         //printf("now:\n\tleft_enegry_sum=%d\tright_enegry_sum=%d\tenegry_sum=%d\n",left_enegry_sum,right_enegry_sum,ans);

     }

     printf("%d\n",ans);

 }

但是在数据来那个很大的情况下会超时。

所以考虑到我们的枚举分界点方向是从左到右，那么我们不需要每次枚举分界点都O(n)地去计算左右手拿物品的能量

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int main()

 {

     int n,l,r,Q_l,Q_r,w[+];

     scanf("%d%d%d%d%d",&n,&l,&r,&Q_l,&Q_r);

     for(int i=;i<=n;i++) scanf("%d",&w[i]); w[]=;

     int ans=,left_energy_sum=,right_energy_sum=;

     for(int i=;i<=n;i++) right_energy_sum+=w[i]*r;

     for(int m=;m<=n;m++) //边界在m右边

     {

         left_energy_sum+=w[m]*l; //分界点右移一位，left_enrgy_sum增加新增的那一个物品消耗的能量即可

         right_energy_sum-=w[m]*r; //分界点右移一位，right_enrgy_sum减少那一个物品消耗的能量即可

         if(m < n-m) //右手拿的东西多

             ans=min(ans , left_energy_sum + right_energy_sum + ( (n-m) - m -  ) * Q_r);

         else if(m > n-m) //左手拿的东西多

             ans=min(ans , left_energy_sum + ( m - (n-m) -  ) * Q_l + right_energy_sum);

         else //两只手拿的一样多

             ans=min(ans , left_energy_sum + right_energy_sum);

         //printf("now:\n\tleft_energy_sum=%d\tright_energy_sum=%d\tenergy_sum=%d\n",left_energy_sum,right_energy_sum,ans);

     }

     printf("%d\n",ans);

 }