POJ 1065 DP

题目链接:http://poj.org/problem?id=1065

有一些木棍,每个有长度 $l_i$ 和重量 $w_i$,要求把这些木棍排成若干两个属性值均不下降的序列($l_i \leq l_{i+1}$ 且 $w_i \leq w_{i+1}$)。问至少要分为多少个这样的序列?

例如对于 $( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , ( 4 , 1 )$,最优解是:最少有两个这样的序列:$[( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 )]$ 和 $[( 1 , 2 ) , ( 2 , 5 )]$。

思路

首先将所有棍子按照 $l_i$ 从小到大排序,问题即转化为:将 $w_i$ 序列划分为 $k$ 个不下降子序列,求 $k$ 的最小值。

这里有一个有趣的结论:$k$ 的最小值等于 $w_i$ 这个序列的最长下降子序列的长度。

证明需要用到离散数学中的反链的知识:http://aleph.math.louisville.edu/teaching/2009FA-681/notes-091119.pdf

1065.cppview raw
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define maxn 5050
using namespace std;

typedef pair<int, int> item;
item a[maxn];
int dp[maxn];

int main() {
int T; cin >> T;
while (T--) {
int n; scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d", &a[i].first, &a[i].second);
sort(a, a + n);
memset(dp, -1, sizeof dp);
for (int i = 0; i < n; i++)
*lower_bound(dp, dp + n, a[i].second, greater<int>()) = a[i].second;
printf("%d\n", lower_bound(dp, dp + n, -1, greater<int>()) - dp);
}
return 0;
}