DP 求调
查看原帖
DP 求调
669924
guozhetao楼主2024/5/5 15:55

RT,93pts,WA on #5

WA 记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
struct cow{
	int a,b;
	friend bool operator <(cow c,cow d) {//重载运算符
		if(c.a == d.a) return c.b < d.b;
		return c.a < d.a;
	}
}node[25005]; 
int ans[25005],min_ans = 1e18;
signed main() {
	scanf("%lld %lld",&n,&t);
	for(int i = 1;i <= n;i++) {
		scanf("%lld %lld",&node[i].a,&node[i].b);
		if(node[i].a != 1)ans[i] = pow(2,32);
		else ans[i] = 1;
	}
	sort(node + 1,node + n + 1);
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j < i;j++) {
			if(node[i].a <= node[j].b + 1) {//i号奶牛接班j号奶牛 
				ans[i] = min(ans[i],ans[j] + 1);
			}
		}
	}
	for(int i = 1;i <= n;i++) {
		if(node[i].b == t and ans[i] != pow(2,32)) {
			min_ans = min(ans[i],min_ans);
		}
	}
	if(min_ans == 1e18)printf("-1\n");
	else printf("%lld\n",min_ans);
    return 0;
}


2024/5/5 15:55
加载中...