社区讨论
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 条回复,欢迎继续交流。
正在加载回复...