洛谷题号:P3928
就写60分的代码(仿照LIS),不想写100分(线段树不会)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<queue> #include<map> #include<list> #include<cstring> #include<cassert> #include<cmath> using namespace std; int n; long long a[5][100050];//把数列看成4行,原来的第三行分为两行,只能连续大于等于(3)或小于等于(4),不能转移 long long dp[5][100050];//dp[i][j]表示从第i行选择第j个数的最长波动序列长度 int main(){ ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= 3; i++){ for (int j = 1; j <= n; j++){ cin >> a[i][j]; } } for (int i = 1; i <= n; i++){//将第三行的数复制到第四行 a[4][i] = a[3][i]; } //dp初始化 for (int i = 1; i <= 5; i++){ dp[i][1] = 1; } //dp转移方程 for (int j = 2; j <= n; j++){//第j个数 for (int k = 1; k < j; k++){ //和LIS相同 //第一行 for (int i = 1; i <= 4; i++){ if (a[1][j] >= a[i][k])dp[1][j] = max(dp[1][j], dp[i][k] + 1); } //第二行 for (int i = 1; i <= 4; i++){ if (a[2][j] <= a[i][k])dp[2][j] = max(dp[2][j], dp[i][k] + 1); } //第三行 for (int i = 1; i <= 3; i++){ if (a[3][j] >= a[i][k])dp[3][j] = max(dp[3][j], dp[i][k] + 1); } //第四行 for (int i = 1; i <= 4; i++){ if (i == 3)continue; if (a[4][j] <= a[i][k])dp[4][j] = max(dp[4][j], dp[i][k] + 1); } } } long long ans = 0; for (int i = 1; i <= 4; i++){ ans = max(ans, dp[i][n]); } cout << ans << endl; return 0; } |