社区讨论
求助大家看看这道题的DP状态和转移有没有什么问题
CF446ADZY Loves Sequences参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @locvntjm
- 此快照首次捕获于
- 2023/10/30 20:29 2 年前
- 此快照最后确认于
- 2023/11/05 07:00 2 年前
QAQ萌新妹子刚学OI,求助求助
我觉得挺好的啊
代码:
CPP#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,ans;
int a[maxn];
int dp[maxn][3];
//dp[i][0/1/2]表示前i位没修改,修改了但是不是i,修改了i的最长长度
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i][0]=1;
}
for(int i=2;i<=n;i++)
{
if(a[i]<=a[i-1])
dp[i][2]=max(dp[i][2],dp[i-1][0]+1);
else
{
dp[i][0]=max(dp[i-1][0]+1,dp[i][0]);
dp[i][1]=max(dp[i][1],max(dp[i-1][2]+1,dp[i-1][1]+1));
}
}
for(int i=1;i<=n;i++)
ans=max(ans,max(dp[i][0],max(dp[i][1],dp[i][2])));
printf("%d\n",ans);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...