[CF355C]Vasya and Robot（思维，贪心）
题目链接：http://codeforces.com/contest/355/problem/C
题意：1~n n个物品各重wi，现在有一个人可以从左边拿和从右边拿， 左边拿一个物品的花费是l*wi，从右边拿是r*wi。然后如果有一次从左边拿的上一次操作也是从左边拿的，就要额外花费ql，同理右边，问最小花费。
眼瞎胡乱跑了一发dp结果T了…
仔细观察就会发现，题意说的是…左手一定从最左边拿，右手一定从最右边拿……
那么一定有一个点，这个点的左手边全是左手拿的，右手边都是右手拿的。
那么枚举这个点，然后再判断这个点左手拿比较好还是右手拿比较好。由于代价都一样，所以可以先计算出两边的分别代价，然后算算某一侧比另一侧多了多少个，也就是需要额外q的花费的个数，贪心地认为这区间是交叉着取的，那么就最后算算多少个q花费就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const LL maxn = 100100; 6 const LL inf = 0x7f7f7f7f; 7 int n, l, r, ql, qr; 8 int w[maxn]; 9 LL ls[maxn], rs[maxn]; 10 LL ret; 11 12 int main() { 13 // freopen("in", "r", stdin); 14 while(~scanf("%d%d%d%d%d",&n,&l,&r,&ql,&qr)) { 15 memset(ls, 0, sizeof(ls)); 16 memset(rs, 0, sizeof(rs)); 17 for(int i = 1; i <= n; i++) scanf("%d", &w[i]); 18 for(int i = 1; i <= n; i++) ls[i] = ls[i-1] + w[i] * l; 19 for(int i = n; i >= 1; i--) rs[i] = rs[i+1] + w[i] * r; 20 ret = inf; 21 for(LL i = 1; i <= n; i++) { 22 LL s = ls[i-1] + rs[i+1]; 23 LL ln = i - 1, rn = n - i; 24 if(ln > rn) ret = min(ret, s+(ln-rn-1)*ql+min(w[i]*l+ql,w[i]*r)); 25 else if(ln < rn) ret = min(ret, s+(rn-ln-1)*qr+min(w[i]*l,w[i]*r+qr)); 26 else ret = min(ret, s+min(w[i]*l,w[i]*r)); 27 } 28 printf("%I64d ", ret); 29 } 30 return 0; 31 }