配对序列P11187: 线性dp

原题

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5e5+10;
constexpr int maxm = 2e6+10;int n;
int wi[maxn];
int dp[maxn][2];
// 题目要求：奇数为和下一个相同，偶数不同  <=>  奇数位和前一个不同，偶数相同
// 在写暴力的时候，可以发现我们奇数位向前找到的最长偶位只有两个可能
// 即当前面最大偶数位的数字和当前数相同，则选择次大且数字不同的偶数位
// 偶数位的更新要找和当前位数字相同的最长奇数位 => 对应奇数位的dp[i][1]
int pos[maxn],lst[maxn];signed main()
{#ifndef ONLINE_JUDGEfreopen("pairing.in","r",stdin);freopen("pairing.out","w",stdout);#endif // ONLINE_JUDGEint n;scanf("%lld",&n);for(int i=1;i<=n;++i){scanf("%lld",&wi[i]);lst[i]=pos[wi[i]];pos[wi[i]]=i;}dp[0][1]=-1e9;  // 初始化一个点的偶位情况为不可达int fis=0,sec=0;// 最优解和次优的最后一个位置for(int i=1;i<=n;++i){// 更新奇数位if(wi[i]==wi[fis])// 和最优解相同{dp[i][1]=dp[sec][0]+1;// 取次长}else{dp[i][1]=dp[fis][0]+1;}dp[i][0]=dp[lst[i]][1]+1;// 用最优奇位的解更新偶数位if(dp[i][0]>=dp[fis][0])// 更新偶数位最优解{if(wi[i]!=wi[fis])// 如果当前的最后的节点和最优解不同，说明是新的最优解，原本的最优解替换次优{sec=fis;}// 如果相同，只更改最优解fis=i;}else if(dp[i][0]>=dp[sec][0])// 更新次优{sec=i;}}printf("%lld",dp[fis][0]);// 输出最大偶位cerr<<clock()*1.0/CLOCKS_PER_SEC<<" s\n";return 0;
}