USACO 2016 US Open Contest, Platinum Problem 1. 262144

答案：
Here's my solution to this problem.

#include
#include
#include

using namespace std;

#define MAXN ((1 << 18) + 10) #define MAXSZ 70 int dp[MAXSZ + 1][MAXN]; int A[MAXN]; int main() { int N; cin >> N;

vector A(N);
for (int i = 0; i < N; i++) { cin >> A[i];
}

int result = 0;
for (int i = 0; i <= MAXSZ; i++) {
for (int j = 0; j < N; j++) {
if (A[j] == i) {
dp[i][j] = j + 1;
result = max(result, i);
} else {
if (i == 0 || dp[i - 1][j] == -1 || dp[i - 1][dp[i - 1][j]] == -1) {
dp[i][j] = -1;
} else {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
result = max(result, i);
}
}
}
dp[i][N] = -1;
}
cout << result << endl;

return 0;
}
Further analysis contributed by Kyle Liu: There is an alternative O(N)O(N) greedy approach. An O(NlogN)O(Nlog⁡N) greedy solution is obvious. We can remove the lowest value (MM) by greedily combining KK consecutive pairs of MM into K/2K/2 pairs of (M+1M+1). In case that KK is odd, we can simply break the sequence into two and assign the K/2K/2 pairs of M+1M+1 to both sequences. Repeating this process will give us an O(NlogN)O(Nlog⁡N) solution, using appropriate data structures.

O(N)O(N) can be achieved since we don't have to always find lowest value to remove. Consider the sequence of numbers as heights of hills. We can simply find the "valley points" (point whose heights are below its neighbours') to remove. We first condense the sequence into consecutive intervals of same heights. We use a stack to keep track of the sequence and "valley point". As we go through the list of intervals, if the stack is empty or the incoming height is below the height in the top of stack (downhill), we simply push the incoming interval to the stack. If the incoming height is above the height in the top of stack (uphill), the point at the top of the stack is a "valley point", and it needs to be removed by combining into its neighbouring intervals. Its left neighbours are in the stack and its right neighbour is the incoming interval. If any combination needs to break into two sequences. We can calculate the optimal value of the first sequence by "collapsing" the stack. We then start the second sequence with only the "valley point" in the stack.

Here is my code implementing this approach:

#include
#include
#include

using namespace std;

#define MAXN 262144+10

struct Node {
int val;
int tot;
};

Node ar[MAXN];
Node s[MAXN];
int N, top = 0, res = 0;

void collapse_stack(void) // calculate value for first squence and reset stack
{
for (; top > 1; top--)
s[top-2].tot += s[top-1].tot / (1 << (s[top-2].val - s[top-1].val)); res = max(res, s[top-1].val + (int)log2(s[top-1].tot)); top--; } void combine_left(int val) // combine the left side until height reaches val { for (; top > 1; top--) {
if(s[top-2].val > val) break;
int num = 1 << (s[top-2].val - s[top-1].val); if (s[top-1].tot % num) { Node tmp = s[top-1]; collapse_stack(); s[top++] = tmp; // start second sequence with the "valley point" break; } s[top-2].tot += s[top-1].tot / num; } } int main(void) { freopen("262144.in","r",stdin); freopen("262144.out","w",stdout); cin >> N;

int st = 0;
for(int i=1; i<=N; i++) { int a; cin >> a;
res = max(res, a);
if(a == ar[st].val) ar[st].tot++;
else {
ar[++st].val = a;
ar[st].tot++;
}
}

for(int i=1; i<=st; i++) {
if (top == 0 || (ar[i].val < s[top-1].val)) { // downhill, add to stack
s[top++] = ar[i];
continue;
}
combine_left(ar[i].val);
int num = 1 << (ar[i].val - s[top-1].val);
if (s[top-1].tot % num == 0) { // combine new interval into stack
s[top-1].val = ar[i].val;
s[top-1].tot = ar[i].tot + s[top-1].tot / num;
}
else { // new intervals cannot be merged to intervals already in stack
ar[i].tot += s[top-1].tot / num;
collapse_stack();
s[top++] = ar[i];
}
}
collapse_stack(); // obtain answer for remaining intervals in stack
cout << res << endl;
return 0;
}