AtCoder Beginner Contest 038 D - プレゼント

問題

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder

解法

箱をh昇順にソートすると、wについてのLIS(最長増加部分列)でいけそうな感じになる。
しかしそのままでは部分列中にhが同じ箱が紛れ込んでしまう場合があるので、hが同じ箱同士ではwの降順にソートするとそんなことは起こらない。
LISは蟻本の65Pのやつでになる。

実装

頭がないのでwの降順ソートした後に色々と余計なことをした。

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MAX_N = 100000;
 
int N;
vector<int> W[MAX_N];
int dp[MAX_N];
 
signed main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int h, w;
		cin >> h >> w; h--; w--;
		W[h].push_back(w);
	}
	fill(dp, dp + N, INT_MAX);
	for (int i = 0; i < MAX_N; i++)
	{
		sort(W[i].begin(), W[i].end()); reverse(W[i].begin(), W[i].end());
		vector<int*> v;
		for (int j = 0; j < W[i].size(); j++)
		{
			v.push_back(lower_bound(dp, dp + N, W[i][j]));
		}
		for (int j = 0; j < W[i].size(); j++)
		{
			*v[j] = W[i][j];
		}
	}
	printf("%d\n", lower_bound(dp, dp + N, INT_MAX) - dp);
	return 0;
}