P3147 [USACO16OPEN]262144 P

第十题 P3147 [USACO16OPEN]262144 P

题目分析

此题为区间 \(DP\) ,却与一般的 \(DP\) 题不同。能够看出是两个相邻区间合并，但是却不知道具体是哪两个区间。

因此，我们需要将区间加入状态描述中。左端点，区间长度，右端点三选二。这里选择左端点和区间长度。

设 \(dp_{i,j}\) 表示以 \(j\) 为左端点合成数字 \(i\) 的区间长度。当区间长度为 \(0\) 时，表示不存在这样的区间。

则可得到状态转移方程：

\(dp[i][j]=dp[i-1][j]+dp[i-1][j+dp[i-1][j]]\)

code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,dp[60][270000],ans;
int main(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<=n;i++) scanf("%d",&x),dp[x][i]=1;
	for(int i=2;i<=58;i++){
		for(int j=1;j<=n;j++){
			if(!dp[i][j]) 
				if(dp[i-1][j]&&dp[i-1][j+dp[i-1][j]])//判断两个区间是否存在 
					dp[i][j]=dp[i-1][j]+dp[i-1][j+dp[i-1][j]];
			if(dp[i][j]) ans=max(ans,i);
		}
	} 
	cout<<ans<<endl;
	return 0;
}

\(i\) 的最大值为 \(58\) 是因为 \(2^{18}=262144\) 且范围为 \(1\sim40\)。

所以 \(i\) 的最大值为 \(40+18=58\)。

summary

算是拓宽了在区间 \(dp\) 解法中的另一种常规思路吧。和 \(ST\) 算法有着异曲同工之妙，也算变相复习了 \(ST\) 算法了。

\(2023.1.29\)