Problem Description:
Mowing the Lawn [Neal Wu, 2008]
After winning the annual town competition for best lawn a year ago,Farmer John has grown lazy; he has not mowed the lawn since thenand thus his lawn has become unruly. However, the competition isonce again coming soon, and FJ would like to get his lawn intotiptop shape so that he can claim the title. Unfortunately, FJ has realized that his lawn is so unkempt that hewill need to get some of his N (1 <= N <= 100,000) cows, who arelined up in a row and conveniently numbered 1..N, to help him. Somecows are more efficient than others at mowing the lawn; cow i hasefficiency E_i (0 <= E_i <= 1,000,000,000). FJ has noticed that cows near each other in line often know eachother well; he has also discovered that if he chooses more than K(1 <= K <= N) consecutive (adjacent) cows to help him, they willignore the lawn and start a party instead. Thus, FJ needs you toassist him: determine the largest total cow efficiency FJ can obtainwithout choosing more than K consecutive cows. PROBLEM NAME: mowlawn
INPUT FORMAT:
* Line 1: Two space-separated integers: N and K
* Lines 2..N+1: Line i+1 contains the single integer: E_i
SAMPLE INPUT (file mowlawn.in): 5 212345
INPUT DETAILS: FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that order. He wants to choose some of the cows such that their total efficiency is maximized, but he cannot choose more than 2 consecutive cows.
OUTPUT FORMAT: * Line 1: A single integer that is the best total efficiency FJ can obtain.
SAMPLE OUTPUT (file mowlawn.out): 12
OUTPUT DETAILS: FJ chooses all cows but the third. The total efficiency of the cows is thus 1 + 2 + 4 + 5 = 12.
This is one problem that requires to use a technique called monotonic queue. We let f[i] equals to the minimum cost by not choosing i, and the elements before i are selected in accordance to the rules. The answer is sum of all of the cow efficiency minus the minimum value of last K costs.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
ll a[maxn],q[maxn],f[maxn],sum;
int N,K;
int main(){
FAST_IO
cin>>N>>K;
for(int i = 1; i <= N; i++) {cin>>a[i]; sum += a[i];}
int head,tail;
head = tail = 0;
for(int i = 1; i <= N; i++){
f[i] = a[i] + f[q[head]];
while(head <= tail && i - q[head] > K) head++;
while(head <= tail && f[i] < f[q[tail]]) tail--;
q[++tail] = i;
}
cout<<endl;
ll mn = f[N];
for(int i = N - K; i <= N; i++) mn = min(mn,f[i]);
cout<<sum - mn<<endl;
return 0;
}