魔法气球 题解

1. O(n^3)的区间dp

dp[i][j]:i~j的区间里的max

注意随时取max，因为最大气球不一定需要合并完所有气球！

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7,M=5e3+7;
int n,ans,d[N],dp[M][M];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>d[i],dp[i][i]=d[i],ans=max(ans,dp[i][i]);
	for(int len = 2;len<=n;len++){
		for(int i = 1;i+len-1<=n;i++){
			int j=i+len-1;
			for(int k = i;k<j;k++){
				if(dp[i][k]==dp[k+1][j]&&dp[i][k])
					dp[i][j]=max(dp[i][j],dp[i][k]+1);
			}ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

（不知道我写没写挂，这个纯暴力dp只能拿个16pts..?

2. O(70n)倍增思想dp

（50+log3e5 = 68 < 70）

dp[i][j]:以j为左端点，能合并出i的区间的最右的右端点

因为每合并一次，两个相邻气球会变成一个直径+1的气球，所以不难发现，“能合并出i的区间”的答案可以从“能合并出i-1的区间”的答案转移而来。根据题意，必须是两个相邻的i-1放在一起才有合并成i的资格，所以可以以j为左端点，向右扩展两个能合并出i-1的区间，此时得到的最右的右端点即为所求（dp[i][j]）。

具体地，以j为左端点，扩展出第一个能合并出i-1的区间时，最右的右端点为dp[i-1][j]；第二次，就要以上一次的右端点为这一次的左端点，不妨设new_j=dp[i-1][j]，再向右扩展出一个能合并出i-1的区间，此时最右的右端点为dp[i-1][new_j]，代入得dp[i-1][dp[i-1][j]]，这就是dp[i][j]的答案。

一些细节：1.初值dp[d[i]][i]=i+1；2.若dp[i][j]未被赋值，则按照上述式子进行状态转移；否则，则记录ans为i。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300001;
int n,ans,d[N],dp[70][N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>d[i];
		dp[d[i]][i]=i+1;
	}
	for(int i = 2;i<=68;i++)
		for(int j = 1;j<=n;j++){
			if(!dp[i][j])dp[i][j]=dp[i-1][dp[i-1][j]];
			if(dp[i][j])ans=i;
		}
	cout<<ans<<'\n';
	return 0;
}

首先看着很像 DP，然后注意到 $d_i$ 都非常小，而且这个气球是相邻的才能合并，合并之后还可以继续跟后边的再合并。所以设 $dp_{i,j}$ 表示以下标 $i$ 为左端点，使得这一段区间的答案为 $j$ 的右端点是多少。

初状态 $dp_{n,d[n]}=n$，我们要求的就是 $max dp_{n,j}$。

然后显然 $dp_{i,d_i}=i$。然后显然如果 $d_i=d_{i+1}$ 则 $dp_{i,{d_i+1}}=i+1$。

但是他不止能够跟他后边的一个合并，合并完了他还可以继续跟后边的合并，所以考虑使用while循环进行连续查找，如果后面的不相等就停止。

#include<bits/stdc++.h>
#define int long long
#define N 300005
using namespace std;
int n,d[N],dp[N][75];
signed main() {
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>d[i];
	}
	dp[n][d[n]]=n;
	for(int i=n-1; i>=1; --i) {
		dp[i][d[i]]=i;
//		if(d[i]==d[i+1]) {
//			dp[i][d[i]+1]=i+1;
//		}
		int nw=d[i],j=i;
		while(1){
			if(dp[j+1][nw]){
				dp[i][nw+1]=dp[j+1][nw];
				j=dp[j+1][nw];
				++nw;
			}else{
				break;
			}
		}
	}
	int ans=0;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=70; ++j) {
			if(dp[i][j])ans=max(ans,j);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

进食后人

对了，虽然他说 $d_i\le 50$，但是他可能会合出来更大的，如果是 $300000$ 个 $50$，最后就合出来 $68$，也就是$50+log_2 300000$。

所以第二维开到 $70$ 就够，但是也不要开太大，如果你开大又恰好喜欢开longlong，就会和我一样喜提0分的好成绩。

可喜可贺。