为啥WA了

原题链接：696.[CSP-J 2022] 上升点列

AC是最好的

2025-10-11 13:05:12

发布于：福建

1阅读

0回复

0点赞

#include <bits/stdc++.h>

using namespace std;

const long long N = 1e3 + 10;
struct point {
	long long x , y;
}a[N];

long long n , k , dp[N][N];

int main( ) {
	cin >> n >> k;
	
	for (int i = 1 ; i <= n ; i++) {
		cin >> a[i].x >> a[i].y;
	};
	
	sort(a + 1 , a + n + 1 , [&](point A , point B) {
		if (A.x != B.x) return A.x < B.x;
		return A.y < B.y;
	});
	
	for (int i = 1 ; i <= n ; i++) {
		for (int j = 0 ; j <= k ; j++) {
			dp[i][j] = j + 1;
			
			for (int t = 1 ; t < i ; t++) {
				if (a[t].x <= a[i].x && a[t].y <= a[i].y) {
					long long d = (a[i].x - a[t].x) + (a[i].y - a[t].y) - 1;
					if (j > d) {
						dp[i][j] = max(dp[i][j] , dp[t][j - d] + d + 1);
					} 
				}
			}
		}
	}
	
	long long ans = 0;
	
	
	for (int i = 1 ; i <= n ; i++) {
		ans = max(ans , dp[i][k]);
	}
	
	cout << ans << endl;

	
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论