恩。。。noip滴时候要刷刷水嘛。。。
DP题
f[i][j]表示到了第i头牛，最后已经连续选了j头牛的方案数
f[i][j] = f[i - 1][j - 1] + v[i] (0 < j < k) 或 f[i - 1][j'] (j = 0且0 < j' < k)
首先。。。第一维可以滚动掉，但是复杂度还是O(n * k)
于是想到了单调队列，q[i]表示队列里第i个选的是哪个位置上的牛
然后就好了，复杂度O(n)~！
1 /************************************************************** 2 Problem: 2442 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:64 ms 7 Memory:1976 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 typedef long long ll; 15 const int N = 100005; 16 int n, k, l, r; 17 ll f[N], ans, tot; 18 int q[N]; 19 20 inline int read(){ 21 int x = 0; 22 char ch = getchar(); 23 while (ch < '0' || ch > '9') 24 ch = getchar(); 25 while (ch >= '0' && ch <= '9'){ 26 x = x * 10 + ch - '0'; 27 ch = getchar(); 28 } 29 return x; 30 } 31 32 int main(){ 33 n = read(), k = read(); 34 int i, x; 35 ans = (ll) 1e15; 36 for (i = 1; i <= n; ++i){ 37 tot += (x = read()); 38 f[i] = x + f[q[l]]; 39 while (f[q[r]] > f[i] && l <= r) --r; 40 q[++r] = i; 41 while (q[l] < i - k) ++l; 42 if (i >= n - k) 43 ans = min(ans, f[i]); 44 } 45 printf("%lld ", tot - ans); 46 return 0; 47 }
（p.s. 谁倒是告诉我那个叫"zhonghaoxi"的巨巨是怎么28ms的。。。总觉得是不科学的，嗯！）