魔法气球 题解

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