记录编号	577270	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2022J]上升点列	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2022-10-29 18:04:24	内存使用	3.13 MiB

#include <bits/stdc++.h>
using namespace std;
int n, k, xi[510], yi[510], f[510][110], dis[510][510], inc[510], ans;
bool vis[510];
vector<int> cd[510], w[510];
signed main() {
	freopen("csp2022pj_point.in", "r", stdin);
	freopen("csp2022pj_point.out", "w", stdout);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) {
		cin >> xi[i] >> yi[i];
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			if(i == j) {
				continue;
			}
			int x = abs(xi[i] - xi[j]) + abs(yi[i] - yi[j]) - 1;
			if(xi[i] >= xi[j] && yi[i] >= yi[j]) {
				cd[i].push_back(j);
				w[i].push_back(x);
				inc[j] ++;
			}
			if(xi[i] <= xi[j] && yi[i] <= yi[j]) {
				cd[j].push_back(i);
				w[j].push_back(x);
				inc[i] ++;
			}
		}
	}
	queue<int> q;
	for(int i = 1; i <= n; i ++) {
		if(inc[i] == 0) {
//		cout << i << ' ';
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = 0; i < cd[u].size(); i ++) {
			int v = cd[u][i];
			inc[v] --;
//			cout << v << ' ';
			if(inc[v] <= 0) {
				q.push(v);
			}
			for(int j = w[u][i]; j <= k; j ++) {
				f[v][j] = max(f[v][j], f[u][j - w[u][i]] + 1);
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j <= k; j ++) {
			ans = max(ans, f[i][j]);
		}
	}
	cout << ans + k + 1 << endl;
	return 0;
}