洛谷P2627 [USACO11OPEN] Mowing the Lawn G
输入输出样例
输入 #1复制
5 2 1 2 3 4 5
输出 #1复制
12
刚开始我的想法就是直接用dp就可以了吧,一个个遍历过去.
先来一个sum预处理一下得到前缀和
for ( i = 1 ; i <= n ; i ++ ) { cin >> a [ i ]; sum [ i ] = sum [ i - 1 ] + a [ i ]; // 前缀和 } 然后设数组dpdp[i][0]代表不放奶牛，
dp[i][0]=max(dp[i-1][0],dp[i-1][1])前一个放和不放里取最大的
dp[i][1]放奶牛，然后在i-m到i里遍历比较
for(int x=i-m;x
dp[i][1]=max(dp[x][0]+sum[i]-sum[x],dp[i][1]);//放入时的最优解
最后输出 max(dp[n][0],dp[n][1]）
然后超时了
0（n*m）还是要优化一下
学完后发现要用上单调队列
#include
using namespace std;
typedef long long ll;
#define maxn 100005
ll sum[maxn], a[maxn], dp[maxn][2], q[maxn]; //q队列存下标
int i, m, n, head, tail;
int main() {
cin >> n >> m;
for (i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];//前缀和
}
head = 1;//队首
tail = 1;//队尾 q[1]=0;而dp[q[head]][0]=dp[1][0]=dp[1][1]=0
for (i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); //不放时取前面的最优情况
while (head <= tail && q[head] < i - m)//维护队首，如果下标小于i-m就让head++
head++;
dp[i][1] = dp[q[head]][0] - sum[q[head]] + sum[i];
//i放入时 q里的是单调队列，递增的，队首的数是最优解
while (head <= tail && dp[q[tail]][0] - sum[q[tail]] < dp[i][0] -sum[i]){
//维护单调队列，比放入i小的元素依次弹出队
//此处有省略：应该是f[q[tail][0]+sum[i]-sum[q[tail]] 美美ac
有参考老师发的代码，侵权即删
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！