TCCC 2003 Semifinal 03

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Dynamic Programming:

State: dp[i][0] means the first i elements' maximum length with the last diff positive.

          dp[i][1] means the first i elements' maximum length with the last diff negative.

If seq[i] > seq[j], diff is positive, that means ith element could be added to the first j elements with the last diff negative.

If seq[i] < seq[j], diff is negative, that means ith element could be added to the first j elements with the last diff positive.

PS: elements might not be distinct.

Source Code:

//Mon Jun  6 01:25:02 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class ZigZag {
public:
    int longestZigZag(vector <int>);
};

int ZigZag::longestZigZag(vector <int> seq) {
    int N = seq.size();
    vector<vector<int> > dp(N, vector<int>(2, 0));
    int ret = 0;
    for(int i=0; i<N; i++){
        dp[i][0] = 1;
        dp[i][1] = 1;
        for(int j=0; j<i; j++){
            if(seq[j] < seq[i])
                dp[i][0] = max(dp[i][0], 1 + dp[j][1]);
            else if(seq[j] > seq[i])
                dp[i][1] = max(dp[i][1], 1 + dp[j][0]);
        }
        ret = max(ret, max(dp[i][0], dp[i][1]));
    }
    return ret;
}


//Powered by [KawigiEdit] 2.0!