2019CCPC-江西省赛 Wave(dp)

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

题目大意:

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

思路

定义$dp[i][j]$为以i为结尾，且前一个数字是j的合法子序列的长度，根据题意，当$i=j$时没有合法的子序列，所以值为0，对于数组中第一个数字来说，只要$i\neq j$那么$dp[i][j]=1$
根据奇偶的数字相同可以简单得到状态转移方程为:$dp[i][j]=dp[j][i]+1$
i就从数组中一个数字一个数字的取

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
//  char ch = getchar(); x = 0;
//  for (; ch < '0' || ch > '9'; ch = getchar());
//  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
const int maxn = 1e5 + 5;
int num[maxn];
int dp[105][105];
int main()
{
    std::ios::sync_with_stdio(false);
#ifdef test
    freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
#ifdef ubuntu
    freopen("/home/time/debug/debug/in", "r", stdin);
    freopen("/home/time/debug/debug/out", "w", stdout);
#endif
    int n, c;
    cin >> n >> c;
    int i;
    wfor(i, 0, n)
    {
        cin >> num[i];
    }
    int ans = 1;
    wfor(i, 0, c + 1)
    /**初始化，对于数组第一个数字num[0]来说只要$i!=j那么$dp[i][j]=1$**/
    {
        if (num[0] == i)
            dp[num[0]][i] = 0;
        else
            dp[num[0]][i] = 1;
    }
    wfor(i, 1, n)
    {
        int j;
        wfor(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;
}