dp + 贪心
从前往后扫描每个数,对于每个数:
情况1:如果现有的子序列的结果都小于当前数, 则创建新子序列
情况2: 将当前数放到结尾大于等于它的最小的子序列后面
#include <iostream>
using namespace std;
const int N = 1020;
int a[N], dp[N], p[N];
int n;
int main()
{
while (cin >> a[n]) {
n++;
}
int ans = 0, cnt = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (a[i] <= a[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
int k = 0;
while (k < cnt && p[k] < a[i]) {
k++;
}
if (k == cnt) {
p[cnt++] = a[i];
}else{
p[k] = a[i];
}
}
cout << ans << endl;
cout << cnt << endl;
return 0;
}
dp + Dilwoth定理
Dilworth定理:对于一个偏序集,最少链划分等于最长反链长度。
Dilworth定理的对偶定理:对于一个偏序集,其最少反链划分数等于其最长链的长度。
也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。
#include <iostream>
using namespace std;
const int N = 1020;
int a[N], dp[N], g[N];
int n;
int main()
{
while (cin >> a[n]) {
n++;
}
int ans = 0, cnt = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
g[i] = 1;
for (int j = 0; j < i; j++) {
if (a[i] <= a[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}else{
g[i] = max(g[i], g[j] + 1);
}
}
ans = max(ans, dp[i]);
cnt = max(cnt, g[i]);
}
cout << ans << endl;
cout << cnt << endl;
return 0;
}