题解 | Cow Hopscotch-牛客假日团队赛1F题
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/918/F
题目描述
The cows have reverted to their childhood and are playing a game similar to human hopscotch. Their hopscotch game features a line of N () squares conveniently labeled 1..N that are chalked onto the grass.
Like any good game, this version of hopscotch has prizes! Square i is labeled with some integer monetary value (
). The cows play the game to see who can earn the most money.
The rules are fairly simple:
* A cow starts at square '0' (located just before square 1; it has no monetary value).
* She then executes a potentially empty sequence of jumps toward square N. Each square she lands on can be a maximum of K () squares from its predecessor square (i.e., from square 1, she can jump outbound to squares 2 or 3 if K==2).
* Whenever she wishes, the cow turns around and jumps back towards square 0, stopping when she arrives there. In addition to the restrictions above (including the K limit), two additional restrictions apply:
* She is not allowed to land on any square she touched on her outbound trip (except square 0, of course).
* Except for square 0, the squares she lands on during the return trip must directly precede squares she landed on during the outbound trip (though she might make some larger leaps that skip potential return squares altogether).
She earns an amount of money equal to the sum of the monetary values of all the squares she jumped on. Find the largest amount of cash a cow can earn.
By way of example, consider this six-box cow-hopscotch course where K has the value 3:
Square Num: 0 1 2 3 4 5 6
+---+ +---+ +---+ +---+ +---+ +---+ +---+
|///|--| |--| |--| |--| |--| |--| |
+---+ +---+ +---+ +---+ +---+ +---+ +---+
Value: - 0 1 2 -3 4 5
One (optimal) sequence Bessie could jump (shown with respective bracketed monetary values) is: 1[0], 3[2], 6[5], 5[4], 2[1], 0[0] would yield a monetary total of 0+2+5+4+1+0=12.
If Bessie jumped a sequence beginning with 0, 1, 2, 3, 4, ... then she would be unable to return since she could not legally jump back to an untouched square.
输入描述:
* Line 1: Two space separated integers: N and K
* Lines 2..N+1: Line i+1 contains a single integer:
输出描述:
* Line 1: A single line with a single integer that is the maximum amount of money a cow can earn
示例1
6 3
0
1
2
-3
4
5
12
解答
dp维护从这个点开始往回跳的最大值，维护一个正数的前缀和，贪心的发现如果往回跳从跳到
，其中的正数一定会被全部取掉。
写出一个的dp之后上单调队列降复杂度即可。
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K;
LL a[maxn];
LL dp[maxn];
LL pre[maxn];
LL Queue[maxn];
int main(){
Sca2(N,K);
for(int i = 1; i <= N ; i ++){
Scl(a[i]);
if(a[i] <= 0) pre[i] = pre[i - 1];
else pre[i] = pre[i - 1] + a[i];
}
int f = 1,t = 0;
for(int j = 2; j <= N ; j ++){ //dp[i] + a[i + 1] - pre[i + 1]
while(f <= t && Queue[f] < j - K) f++;
if(j - 2 >= 0){
while(f <= t && dp[Queue[t]] - pre[Queue[t]] <= dp[j - 2] - pre[j - 2]) t--;
Queue[++t] = j - 2;
}
dp[j] = dp[Queue[f]] - pre[Queue[f]] + a[j] + a[j - 1] + pre[j - 2];
}
LL ans = dp[1] + pre[min(1 + K,N)];
for(int i = 2; i <= N ; i ++){
dp[i] += pre[min(i + K - 1,N)] - pre[i];
ans = max(ans,dp[i]);
//if(i < N) ans = max(ans,dp[i] + a[i + 1]);
}
Prl(ans);
return 0;
}
