USACO OPEN 2016 Platinum 262144

发表于   |  

看了题解之后mengbi了，原来这么简单。但是为什么比赛的时候就是没有想到呢？大概是我DP的功力还是太浅了。

Description

Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.
She is particularly intrigued by the current game she is playing. The game starts with a sequence of $N$ positive integers ($2≤N≤262,144$), each in the range $1…40$. In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number present in the sequence at the end of the game. Please help Bessie score as highly as possible!

INPUT FORMAT (file 262144.in):

The first line of input contains N, and the next N lines give the sequence of N numbers at the start of the game.

OUTPUT FORMAT (file 262144.out):

Please output the largest integer Bessie can generate.

SAMPLE INPUT:

4
1
1
1
2

SAMPLE OUTPUT:

3

In this example shown here, Bessie first merges the second and third 1s to obtain the sequence 1 2 2, and then she merges the 2s into a 3. Note that it is not optimal to join the first two 1s.

Sol

考场上我用区间DP得了样例分（囧

通过计算器计算，我们可以发现，$262144 = 2^{18} $
那么这样的话很明显是用类似倍增之类的手段处理。

这里有一个非常巧妙的建模方法：
$f[p][i]$表示从i为起点，最大值为P的终点的值（无法实现即为-1）
则有递推方程式：
$f[p+1][i] = f[p][f[p][i]+1]$

问题迎刃而解。

Origin Sol

(Analysis by Mark Gordon)
A simple way to approach this problem would be to consider all ranges of the input array and determine the largest number that can be produced in that range. However, most ranges aren’t actually interesting as they could never be combined into one.

To see this it helps to look at the equivalent problem where each of the array elements are powers of two and instead of combining x and x to produce x + 1 you produced 2x. Now it’s clear that a range must sum to a power of two to be interesting. In fact, an interesting range can be better described by its starting position and the power of two it sums to.

This informs a simple Dynamic Programming solution. We let DP[p][i] give the ending index of the range starting at i that can combine to p, or -1 if it doesn’t exist. DP[p + 1][i] is then calculated as DP[p + 1][i] = DP[p][DP[p][i]] provided DP[p][i] is valid.

Here’s my solution to this problem.

Code

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
40
41
#include <iostream>
#include <cstdio>
#include <vector>

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<int> 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;
}