[DP 區間 轉移限制] P3146 [USACO16OPEN]248 G

題目

思路

考慮轉移條件：相鄰且值相同

如何保證相鄰，直接區間DP本身就是考慮相鄰兩塊的。

值相同，區間DP左半塊和右半塊相同即可

i f ( f [ i ] [ k ] = = f [ k + 1 ] [ j ] ) f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ k + 1 ] + 1 ) if(f[i][k]==f[k+1][j])f[i][j]=max(f[i][j],f[i][k+1]+1) if(f[i][k]==f[k+1][j])f[i][j]=max(f[i][j],f[i][k+1]+1)

由于轉移受限制，最終區間 f [ 1 ] [ n ] f[1][n] f[1][n]不一定可以合成出來，是以對所有區間取max作為答案

代碼

// Problem: P3146 [USACO16OPEN]248 G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3146
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// FishingRod

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY

*/
int T;
const int N=258;
int a[N];
LL f[N][N];
void solve(int C)
{
	//NEW DATA CLEAN
	
	//NOTE!!!
	int n;cin>>n;
	LL ans=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)f[i][i]=a[i];
	for(int len=2;len<=n;len++)
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			for(int k=l;k<r;k++){
				if(f[l][k]==f[k+1][r]&&f[l][k]&&f[k+1][r])f[l][r]=max(f[l][r],f[l][k]+1);
				ans=max(ans,f[l][r]);
			}
		}
	cout<<ans;
}

int main()
{
	#ifdef MULINPUT
		scanf("%d",&T);
		for(int i=1;i<=T;i++)solve(i);
	#else
		solve(1);
	#endif
	return 0;
}