1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <vector>
#include <queue>
using namespace std;
int minRewards(vector<int> scores) {
if(scores.size() <= 1) return scores.size();
int n = scores.size();
queue<array<int,3>> q;
vector<int> dp(n, 1);
for(int i = 0; i < n; i++) {
if(i == 0) {
if(scores[i] < scores[i+1]) {
q.push({i + 1, 1, 2});
}
} else if(i == n -1) {
if(scores[i-1] > scores[i]) {
q.push({i - 1, -1, 2});
}
} else {
if(scores[i] < scores[i+1] and scores[i-1] > scores[i]) {
q.push({i-1, -1, 2});
q.push({i+1, 1, 2});
}
}
}
while(!q.empty()) {
auto [pos, dir, newScore] = q.front(); q.pop();
dp[pos] = max(dp[pos], newScore);
int next = pos + dir;
if(0 <= next and next < n and scores[next] > scores[pos]) {
q.push({next, dir, dp[pos] + 1});
}
}
return accumulate(begin(dp), end(dp), 0);
}
|
