AcWing 3505. 最长ZigZag子序列
原题链接
简单
作者:
faith_9
,
2021-05-17 20:16:01
,
所有人可见
,
阅读 506
算法1
DP
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int a[55],n;
int f[55][2];//f[i][0]以第i个数结尾且前一个数比第i个数大的方案数;
//f[i][1]以第i个数结尾且前一个数比第i个数小的方案数;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int res=1;
f[1][1]=f[1][0]=1;
for(int i=1;i<=n;i++)//循环以第i个数结尾的方案数
{
for(int j=0;j<=1;j++)//循环每种可能
{
for(int k=1;k<i;k++)//从1~i-1枚举前一种状态,即以第k个数结尾的方案数
{
if(a[k]>a[i]&&!j)f[i][j]=max(f[k][!j]+1,f[i][j]);//参考f[i][j]的定义
if(a[k]<a[i]&&j) f[i][j]=max(f[k][!j]+1,f[i][j]);
}
res=max(f[i][j],res);//求最大值;
}
}
cout<<res;
return 0;
}