题意：给出长度为 n 的序列，要找出两个非空的子序列，这两个子序列要满足：相邻两个元素相差 1 或相差 7 的倍数。 问两个子序列的长度和的最大值。
tags：容易想到 dp[i][j] 表示选择两个子序列分别以第 i 个元素和第 j 个元素结尾的最大长度和 。但难在怎么转移。
设 i < j ， k<j， 则 dp[i][j] 只能从 dp[i][k] 转移，而不能从 dp[k][j] 转移，因为我们不能保证第二个子序列是否用到第 k 个元素。
然后用数组 maxmod[i] 维护 ai%7 == i 的最大dp[i][j]， maxnum[i] 维护 ai == i 的最大的 dp[i][j] 。
我们只要固定一个 i， 对于每个 i ，初始化一遍 maxmod[] 和 maxnum[]， 然后枚举 j 从 i+1~n ， 更新 dp[i][j] 即可。
dp[i][j] 有可能从 a[j]+1、a[j]-1、maxmod[a[j]%7] 或 dp[i][0] (即第 j 个元素新开一个序列) 转移而来， 在转移的同时更新 maxmod[] 和 maxnum[] 。
另外， dp[j][i] 要由 dp[i][j] 得到，这点容易忽略。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 5005; int n, a[N], dp[N][N], maxmod[10], maxnum[100005]; int main() { scanf("%d", &n); rep(i,1,n) scanf("%d", &a[i]); int ans=0; rep(i,0,n) { mes(maxmod, 0); mes(maxnum, 0); rep(j,0,i) { maxmod[a[j]%7] = max(maxmod[a[j]%7], dp[i][j]); maxnum[a[j]] = max(maxnum[a[j]], dp[i][j]); } rep(j,i+1,n) { dp[i][j] = max(maxnum[a[j]+1]+1, dp[i][j]); dp[i][j] = max(maxnum[a[j]-1]+1, dp[i][j]); dp[i][j] = max(maxmod[a[j]%7]+1, dp[i][j]); dp[i][j] = max(dp[i][0]+1, dp[i][j]); maxnum[a[j]] = max(maxnum[a[j]], dp[i][j]); maxmod[a[j]%7] = max(maxmod[a[j]%7], dp[i][j]); dp[j][i] = dp[i][j]; ans = max(ans, dp[i][j]); } } printf("%d ", ans); return 0; }