社区讨论

8分区间DP求助

P3146[USACO16OPEN] 248 G参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2vm87h
此快照首次捕获于
2023/10/23 20:30
2 年前
此快照最后确认于
2023/10/23 20:30
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
long long f[250][250][3],a[250],n;
int main(){
	cin>>n;
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		f[i][i][0]=f[i][i][1]=f[i][i][2]=a[i];
	for(int l=2;l<=n;l++)
		for(int i=1;i<=n-l+1;i++){
			int j=i+l-1;
			if(a[i]==a[i+1])
				f[i][j][1]=max(f[i+1][j][1]+1,a[i]);
			else
				f[i][j][1]=a[i];
			if(a[j]==a[j-1])
				f[i][j][2]=max(f[i][j-1][2]+1,a[j]);
			else
				f[i][j][2]=a[j];
			f[i][j][0]=max(f[i][j-1][0],max(f[i+1][j][0],max(f[i][j][1],f[i][j][2])));
		}
	cout<<f[1][n][0];
	return 0;		
}

回复

1 条回复,欢迎继续交流。

正在加载回复...