nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cf521F2

链接

http://codeforces.com/contest/1077/problem/F2

题意

        给你n个点，每个点有个权值a[i]，可以在n个点中选x个特殊点，要保证最后的序列中每连续k个点都至少有一个特殊点，问x个特殊点的权值和最大可以是多少
        1<=k,x<=n<=5000
        1<=k,x<=n<=5000

题解

        dp[i][j]前i个点选j个特殊点，且第j个点在位置i
        dp[i][j]=max(dp[ii][j-1]) i-ii-1<=k
        先不管j，维护一个i单调增，dp值单调减的队列即可。