卧薪尝胆,厚积薄发。
USACO2016OPEN PLATINUM 262144
Date: Wed Sep 19 17:15:34 CST 2018
In Category:
NoCategory
Description:
给
$n$
个数,每次可以把相邻两个相同的数合成比他们大一的数,问最后最终能得到的最大的数是多少。
$1\le n \le 270000,1\le a_i\le 40$
Solution1:DP
$f[i][j]$
表示
$i$
位置上的数合成数
$j$
的区间右端点
$+1$
最小是多少,转移为
$f[i][j]=f[f[i][j-1]][j-1]$
。
Code1:
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define MAXN 270010
int n;
int a[MAXN];
int f[MAXN][61];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
memset(f,0,sizeof(f));
for(int i = 1;i <= n;++i)f[i][a[i]] = i + 1;
int ans = 0;
for(int i = 2;i <= 60;++i)
{
for(int j = 1;j <= n;++j)
{
if(!f[j][i])f[j][i] = f[f[j][i - 1]][i - 1];
if(f[j][i])ans = i;
}
}
cout << ans << endl;
return 0;
}
Solution2:贪心
从小到大枚举每个数,如果连续的偶数项,那么显然两两合成,如果奇数项,那么最终一定会剩一个,也就是说两边必定分离,那就每边
$\frac{i+1}2$
个,中间用
$-1$
分隔开即可。
Code2:
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡