代码过了样例,但是只有82分,求助!
查看原帖
代码过了样例,但是只有82分,求助!
804607
rainygame楼主2023/4/5 08:58
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1001

int c, h, b, ans = 0x7f7f7f7f;
int f[MAXN][MAXN][2];

struct Node{
	int x, t;
}a[MAXN];

bool cmp(Node a, Node b){
	return a.x < b.x;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> c >> h >> b;
	for (int i=1; i<=c; i++) cin >> a[i].x >> a[i].t;
	sort(a+1, a+c+1, cmp);
	
	memset(f, 0x3f, sizeof(f));
	f[1][c][0] = max(a[1].x, a[1].t);
	f[1][c][1] = max(a[c].x, a[c].t);
	
	for (int i=1; i<=c; i++){
		for (int j=c; j>=i; j--){
			f[i][j][0] = min(f[i][j][0], max(f[i-1][j][0]+a[i].x-a[i-1].x, a[i].t));
	        f[i][j][0] = min(f[i][j][0], max(f[i][j+1][1]+a[j+1].x-a[i].x, a[i].t));
	        f[i][j][1] = min(f[i][j][1], max(f[i-1][j][0]+a[j].x-a[i-1].x, a[j].t));
	        f[i][j][1] = min(f[i][j][1], max(f[i][j+1][1]+a[j+1].x-a[j].x, a[j].t));
		}
	}
	
	for (int i=1; i<=c; i++) ans = min(ans, min(f[i][i][0], f[i][i][1])+abs(b-a[i].x));
	cout << ans;
	
	return 0;
}

2023/4/5 08:58
加载中...