首页 > 代码库 > BZOJ2442 [Usaco2011 Open]修剪草坪
BZOJ2442 [Usaco2011 Open]修剪草坪
恩。。。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\n", tot - ans);46 return 0;47 }
（p.s. 谁倒是告诉我那个叫"zhonghaoxi"的巨巨是怎么28ms的。。。总觉得是不科学的，嗯！）
BZOJ2442 [Usaco2011 Open]修剪草坪
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。