[题目链接]

题目描述

Bessie喜欢在手机上下游戏玩(……),然而她蹄子太大,很难在小小的手机屏幕上面操作。

她被她最近玩的一款游戏迷住了,游戏一开始有n个正整数,(2\leq n\leq262144),范围在1-40。在一步中,贝西可以选相邻的两个相同的数,然后合并成一个比原来的大一的数(例如两个7合并成一个8),目标是使得最大的数最大,请帮助Bessie来求最大值。

题解

难点主要在状态设计,观察题目:发现 2 ^ {18} = 262144,那么最大的结果就是58。数值比较小,考虑枚举每种答案。由于当前数值可能需要两段区间转移而来,而我们需要一个东西标记区间。那么就可以设 dp_{i,j} 表示合并到i的数字,右端点为j,最优(大)的左端点。

那么就有:
dp_{i,j} = dp[i – 1][dp[i – 1][j]]

时间复杂度\mathcal{O}(n),常数58。

注意一下细节,由于值是左端点,可能为0,初始化为-1

update:其实不用取最大,答案严格,直接递推即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 3e5;
int a[MAXN], dp[60][MAXN];
/*
dp[i][j]表示合并到i的数字,右端点为j,最优(大)的左端点
*/
int n;
int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d", &n);
  memset(dp, -1, sizeof(dp));
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    dp[a[i]][i] = i - 1;//这个东西要注意一下
  }
  int ans = 1;
  for(int i = 2; i <= 58; i++) {
    for(int j = 1; j <= n; j++) {
      if(dp[i - 1][dp[i - 1][j]] != -1) dp[i][j] = dp[i - 1][dp[i - 1][j]];
      if(dp[i][j] != -1) ans = i;
    }
  }
  printf("%d\n", ans);
  return 0;
}