P3146 [USACO16OPEN]248 G （区间DP）

P3146 [USACO16OPEN]248 G （区间DP）

题目传送门

思路：

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300;
int a[N],dp[N][N];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),dp[i][i]=a[i];
	int ans=0;
	for(int len=2;len<=n;len++)
		for(int l=1,r=l+len-1;r<=n;l++,r++)
		{
			for(int k=l;k<r;k++)//分割区间 k是左部分区间右端. 
			{
				//printf("dp[%d][%d]=%d,dp[%d][%d]=%d\n",l,k,dp[l][k],k+1,r,dp[k+1][r]);
				if(dp[l][k]==dp[k+1][r]&&dp[l][k])
				{
					 dp[l][r]=max(dp[l][r],dp[l][k]+1);
					 ans=max(dp[l][r],ans);
				}
				/*printf("dp[%d][%d]=%d\n",l,r,dp[l][r]); puts(""); */
			}
		}
	printf("%d\n",ans);
	return 0;
}