题解 – P3147 [USACO16OPEN] 262144 P

[题目链接]

题目描述

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