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)。
转移用单调队列优化。