CF4D Mysterious Present 题解
这道题是一道二维 LIS 问题。
我们知道，一维的 LIS 有 \(O(n^2)\) 和 \(O(n \log n)\) 两种解法。考虑到这道题要输出方案，而且 \(1 \leq n \leq 5000\)，那么在这道二维的 LIS 问题当中我们可以使用 \(O(n^2)\) 的算法来解决这道题。
下面的所有叙述都只考虑 \(w_i > w,h_i > h\) 的物品。
那么根据一维 LIS 问题的知识，我们可以推出状态转移方程：
\[f_i = \max\{f_j+1|j初始 \(f_i=1\)。
但是你这样写你会发现样例都过不去。为什么？
看看样例二或者英文题面，你就会发现 物品顺序可以调换。
因此我们这道题要稍微改一下。
面对这种题目，要使上升子序列长度最大化，我们就需要首先按照 \(w\) 升序排序，这样我们控制住了 \(w\) ，只需要考虑 \(h\)。
所以我们的状态转移方程就要改写成这样：
\[f_i = \max\{f_j+1|j如果你认为这个转移方程是对的，那么恭喜你，掉坑里了。
因为题目中很明确的告诉你了：求最长二维严格上升子序列及其长度。
或许有的读者会问了：我不是已经按照 \(w\) 排序了吗？为什么这样还是错的？
理由很简单：如果 \(w_i = w_{i + 1},h_i < h_{i+1}\)，那么此时 \(i,i+1\) 不符合题目要求，但是根据上面的转移方程我们会统计。
因此最后我们的状态转移方程是这样的：
\[f_i = \max\{f_j+1|j或者这样：
\[f_i = \max\{f_j+1|j而对于那些 \(w_i \leq w\) 或者 \(h_i \leq h\) 的，直接过滤即可。
代码：
#include
using namespace std;
typedef long long LL;
const int MAXN = 5000 + 10;
int n, f[MAXN], las[MAXN], wz, hz, cnt;
struct node
{
int w, h, id;
}a[MAXN];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
return sum * fh;
}
bool cmp(const node &fir, const node &sec)
{
if (fir.w ^ sec.w) return fir.w < sec.w;
return fir.h < sec.h;
}
void print(int k)
{
if (k == -1) return ;
print(las[k]); printf("%d ", a[k].id);
}
int main()
{
n = read(), wz = read(), hz = read();
for (int i = 1; i <= n; ++i)
{
int w = read(), h = read(); las[i] = -1;
if (w <= wz || h <= hz) continue;
a[++cnt].w = w; a[cnt].h = h; a[cnt].id = i;
}
if (cnt == 0) {printf("0\n"); return 0;}
sort(a + 1, a + cnt + 1, cmp);
for (int i = 1; i <= cnt; ++i)
{
f[i] = 1;
for(int j = 1; j < i; ++j)
{
if (a[j].w < a[i].w && a[j].h < a[i].h && f[j] + 1 > f[i])
{
f[i] = f[j] + 1;
las[i] = j;
}
}
}
int ans = 0, flag = 0;
for (int i = 1; i <= cnt; ++i)
{
if (f[i] > ans)
{
ans = f[i];
flag = i;
}
}
printf("%d\n", ans); print(flag);
return 0;
}