2083. ZigZag

10152130220

作个参考

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;
}

10152130146

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

10152130146

容易出错的数据
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

MasterKiller

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

世界弹射物语玩家

看题目以为是个splay

10175102262 LarsPendragon

这是道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;
}
你当前正在回复 博客/题目
存在问题!