36分求助
查看原帖
36分求助
1312482
Delightedppp楼主2025/1/23 14:24

只A了前4个点,后三个点超时

#include<bits/stdc++.h>
using namespace std;
struct node{
	int l;
	int w;
}a[5001];
int n,cnt,ans,dp[5001]; 
bool b[5001];
bool cmp(node a,node b){
	if(a.l!=b.l)
		return a.l>b.l;
	return a.w>b.w;
}
int main() {
	cin>>n;
	cnt=n;
	for(int i=1;i<=n;i++)
		cin>>a[i].l>>a[i].w;
	sort(a+1,a+n+1,cmp);
	while(cnt>0){
		int p[5001]={0},k=0,ad;
		for(int i=1;i<=n;i++)
			dp[i]=1;
		for(int i=1;i<=n;i++){
			if(!b[i]){
				for(int j=i-1;j>=1;j--){
					if(!b[j]&&a[j].w>=a[i].w&&a[j].l>=a[i].l){
						if(dp[j]+1>dp[i]){
							p[i]=j;
							dp[i]=dp[j]+1;
						}
					}
				}
			}
		}
		for(int i=n;i>=1;i--){
			if(!b[i]){
				if(k<dp[i]){
					k=dp[i];
					ad=i;
				}
			}
		}
		while(p[ad]!=0){
			b[ad]=1;
			ad=p[ad];
			cnt--;
		}
		b[ad]=1;
		cnt--;
		ans++;
	}
	cout<<ans;
	return 0; 
}
2025/1/23 14:24
加载中...