# 江西ccpc省赛-waves-(DP做法)

江西ccpc省赛-waves-(DP做法)

题链：http://acm.hdu.edu.cn/showproblem.php?pid=6570

• 题意：给你长度为N,1≤N≤100000的一个数组，其中元素在[1,c]1≤c≤100 之内，求一个最长的子序列满足奇数位数字都相同，偶数位数字也都相同,但是奇偶位之间不同，问你子序列的长度。

• 解法1：c的范围较小，由这几个性质可知，序列中只包含两个数字，可以在c的范围内枚举这两个数字。先保存一下每个数字出现的位置。

AcCode:

#include <bits/stdc++.h>

using namespace std;

#define fre freopen("C:\\Users\\22765\\Desktop\\in.txt","r",stdin);

#define ms(a) memset((a),0,sizeof(a))

#define re(i,a,b) for(int (i)=(a);(i)<(b);(i)++)

#define sf(x) scanf("%d",&(x))

#define rg register

#define il inline

typedef long long LL;

const int inf=(0x7f7f7f7f);

const int maxn=3000;

vector<int> v[105];

int main(){

	int n,c;

	sf(n);sf(c);

	int x;

	re(i,0,n){

		sf(x);

		v[x].push_back(i);

	}

	int res=0,len;

	int p,q,fir,sec;

	bool f;

	re(i,1,c+1){

		if(v[i].size()==0)continue;

		re(j,1,c+1){

			if(i==j)continue;

			p=q=0;len=0;

			fir=sec=-1;f=1;

			while(p<v[i].size()&&q<v[j].size()){

				if(f){

					while(p<v[i].size()&&v[i][p]<sec)p++;

					if(p<v[i].size()){

						fir=v[i][p],len++,f=0;

					}

				}

				else {

					while(q<v[j].size()&&v[j][q]<fir)q++;

					if(q<v[j].size()){

						len++,sec=v[j][q],f=1;

					}

				}

			}

			res=max(res,len) ;

		}

	}

	printf("%d\n",res) ;

	return 0;

}

• 解法2：\(dp[i][j]\)表示以i结尾，前一个数是j的序列长度，\(dp[i][i]=0\)，\(i\) \(!=j\)时，\(dp[i][j]=dp[j][i]+1\)，对于每一个位置，预处理以当前数结尾，前一个数是\([1，c]\)中任一一个数的所有情况。

AcCode:

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

#define re(i,a,b) for(int (i)=(a);(i)<(b);++(i))

const int maxn = 1e5 + 5;

int num[maxn];

int dp[105][105];

int main()

{

    std::ios::sync_with_stdio(false);

    int n, c;

    cin >> n >> c;

    int i;

    re(i, 0, n)

    {

        cin >> num[i];

    }

    int ans = 1;

    re(i, 0, c + 1){

    //初始化，对于数组第一个数字num[0]来说只要$i!=j那么$dp[i][j]=1$

    //这里为什么是1而不是2，因为可以确定的数只有dp数组的前一个参数,

    //第二个参数是不确定的

        if (num[0] == i)

            dp[num[0]][i] = 0;

        else

            dp[num[0]][i] = 1;

    }

    re(i, 1, n)

    {

        int j;

        re(j, 0, c + 1)//对原序列的每一个位置，预处理第二个参数的所有情况

        {

            if (num[i] == j)

                dp[num[i]][j] = 0;

            else

                dp[num[i]][j] = dp[j][num[i]] + 1;//状态转移

            ans = max(ans, dp[num[i]][j]);//记录答案

        }

    }

    cout << ans << endl;

    return 0;

}