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

*/