2018-11-18
转载请注明出处：http://tokitsukaze.live/
题目链接：http://codeforces.com/contest/1077
A：
ans=(a-b)*(k/2)+a*(k%2)
B：
贪心。从前往后判断，如果要关灯，先关后面的。
C：
预处理前缀max与后缀max，求出整个数组的和。枚举每个数直接判断即可。
D：
二分答案，check是否合法，最后把序列弄出来即可。
E：
出现个数最多的肯定当最后一项，第二多的肯定当倒数第二项…从多往少枚举，每次调整整个序列的值，取max即可。复杂度O(n)。
F1&F2：
dp[i][j]表示前i个数，ai必选，共选了j个的最大值。
转移：dp[i][j]=max(dp[l][j-1]+a[i]), (i-k≤l＜i)。
ans=max(dp[i][x]), (n-k+1≤i≤n)。
转移用单调队列优化。