- 软件开发
- CH5101--LICS(两种dp)
最长公共上升子序列–Longest-Common -Increasing-Subsequence(LCIS)
如题
状态：dp[i][j] 表示以a[0]-a[i],b[0]-b[j]可以构成的以b[j]结尾的LCIS的长度：
状态转移方程：
a[i] == b[j]a[i] != b[j]
dp[i][j] =
m
a
x
(
d
p
[
i
−
1
]
[
k
]
)
+
1
其
中
0
<
=
k
<
j
,
b
[
k
]
<
a
[
i
]
max(dp[i -1][k]) + 1 其中 0<=k<j, b[k] < a[i]
max(dp[i−1][k])+1其中0<=k<j,b[k]<a[i]dp[i][j] = dp[i - 1][j]
#include<bits/stdc++.h>
#define maxn 3003
#define _rep(i, a, b) for(int i = (a); i <= (b); i++)
#define _for(i, a, b) for(int i = (a); i < (b); i++)
using namespace std
;
int n
, a
[maxn
], b
[maxn
], dp
[maxn
][maxn
];
int main() {
ios
::sync_with_stdio(0);
cin
>> n
;
_rep(i
, 1, n
)cin
>> a
[i
];
_rep(i
, 1, n
)cin
>> b
[i
];
_rep(i
, 1, n
) {
int val
= 0;
_rep(j
, 1, n
) {
if (a
[i
] == b
[j
]) dp
[i
][j
] = val
+ 1;
else dp
[i
][j
] = dp
[i
- 1][j
];
if (b
[j
] < a
[i
])val
= max(val
, dp
[i
- 1][j
]);
}
}
int out
= 0;
_rep(i
, 1, n
) {
out
= max(out
, dp
[n
][i
]);
}
cout
<< out
<< endl
;
system("pause");
}
