2083. ZigZag

作个参考

include

include

include

include

include

using namespace std;

define REP(i,n) for (int i=0;i<n;i++)

int a[10000];
int n;
int f[10000][3];

int main() {
freopen(“1.in”, “r”, stdin);
cin >> n;
REP(i, n) {
cin >> a[i];
f[i][0] = f[i][1] = 1;
}
int ans = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++) {
if (a[i] - a[j] < 0) //now positve
f[i][1] = max(f[j][0] + 1, f[i][1]);
if (a[i] - a[j] > 0 )
f[i][0] = max(f[j][1] + 1, f[i][0]);
ans = max(ans, max(f[i][0], f[i][1]));
}
cout << ans << endl;
}

此处Shut down MasterX 记录
顺便说下，楼上的思路挺好的。

看题目以为是个splay

这是道DP题？？？？
感觉不像，附C代码：

#include <stdio.h>
int main()
{
    int n, num[50], i, j, sign, cnt=0;
    scanf("%d",&n);
    for(i=0; i<n; i++) scanf("%d",&num[i]);
    for(i=0; i<n; i++)
    {
        if(num[i+1]>num[i]) {sign=1; break;}
        else if(num[i+1]<num[i]) {sign=-1; break;}
    }
    for(; i<n-1; i++)
    {
        if(num[i]==num[i+1]) continue;
        if(sign==1) {if(num[i]<num[i+1]) {cnt++; sign*=-1;}
        }
        else if(sign==-1) {if(num[i]>num[i+1]) {cnt++; sign*=-1;}}
    }
    printf("%d\n",cnt+1);
    return 0;
}

容易出错的数据
写错了
5
1 5 2 1 2
答案 4

容易出错的数据
4
1 5 2 1 2
答案 4

50
374 40 854 203 203 156 362 279 812 955 600 947 978 46 100 953 670 862 568 188 67 669 810 704 52 861 49 640 370 908 477 245 413 109 659 401 483 308 609 120 249 22 176 279 23 22 617 462 459 244
答案 36