【题解】洛谷：P4805 [CCC2016] 合并饭团

P4805 [CCC2016] 合并饭团

希望写完这篇题解能真正地会这种题。

合并两个的操作很像合并石子的操作，确实直接那么做就可以，但三个怎么办呢，暴力做法就是枚举中间两个端点然后转移，但是这样复杂度太大了有 \(O(n^4)\)。

于是搬出我们的双指针，在面对区间问题时双指针可以有效地解决问题，但是我们不能瞎用，双指针也要满足单调性才能用，我们一个区间的和是固定的，区间长度越大值就越大，所以我们我们不断调整中间区间的两个端点 \(k,t\)，使得两边到 \(l,r\) 的距离相同，哪边小动哪边的端点，就可以合并了。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
const int N=5e5+10;
const int mod=998244353;
using namespace std;

int n;
int f[100][100];
int ans;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>f[i][i];
		ans=max(ans,f[i][i]);
	}
	
	for(int len=2;len<=n;len++){
		for(int l=1,r=len;r<=n;l++,r++){
			
			for(int k=l;k<r;k++){
				if(f[l][k]==f[k+1][r]){
					f[l][r]=f[l][k]+f[k+1][r];
				}
			}
			
			for(int k=l,t=r;k+1<=t-1;){
				if(f[l][r]){
					break;	 
				}
				if(!f[l][k]){
					k++;
				}
				else if(!f[t][r]){
					t--;
				}
				else if(f[l][k]==f[t][r]){
					if(f[k+1][t-1]){
						f[l][r]=f[l][k]+f[k+1][t-1]+f[t][r];
					}
					else{
						k++;
						t--;
					}
				}
				else if(f[l][k]<f[t][r]){
					k++;
				}
				else if(f[l][k]>f[t][r]){
					t--;
				}
			}
			ans=max(ans,f[l][r]);
		}
	}
	cout<<ans;
	return 0;
}