Codeforces 355C 策略题

题目链接：http://codeforces.com/problemset/problem/355/C

题意：

给定n个杠铃的重量，问把所有杠铃举一次需要的最小能量

1、每次只能举最左边或最右边的一个杠铃

2、举一个杠铃可以用左手或右手，花费为 wi * l (wi*r)

3、若这次用左手，上次也是用左手，则要多花费 Ql 的能量。若连续用右手则要多花费Qr

显然我们最后会举一个杠铃，设为 i

则举[1,i-1]的杠铃都是用左手， 举[i+1, n]的都是用右手，则这里花费的基础能量可以用前缀和求出

而对于 第i个，我们分为

1、用左手举

2、用右手举

则此时基础能量已经确定，为了使得花费最小，则连续使用一只手的情况要尽可能小，显然是交替使用最少

暴力枚举最后举第i个杠铃 和 用左手还是右手举这个杠铃即可

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; #define N 100005 #define ll __int64 #define eps 1e-7 #define inf 1029385391204938 bool equ(double x, double y=0.0){return ((x-y>0) x-y:y-x)
           
            rt)lt-=rt, rt=0; else rt-=lt, lt = 0; if(lt)lt--; else if(rt)rt--; now += lt*ql + rt*qr; ans = min(ans, now); } for(i = 1; i <= n; i++) { ll now = 0;//对于这个点 左手举起 now += Sum(0, 1, i-1); now += Sum(1,i, n); ll lt = i-1, rt = n-i+1; if(lt>rt)lt-=rt, rt=0; else rt-=lt, lt = 0; if(lt)lt--; else if(rt)rt--; now += lt*ql + rt*qr; ans = min(ans, now); } printf("%I64d\n",ans); } return 0; } /* 3 4 4 19 1 42 3 99 4 7 2 3 9 1 2 3 4 */