小圆前辈去爬山

第一行两个整数 n，q 表示有n座山，q次询问。

接下来有n行，每行有两个整数a，h表示山的编号，和编号为a的山的高度。

接下来有q行，每行有两个整数x，w表示小圆前辈在编号为x的山上，拥有的体力值为w。

C++(clang++11) 解法, 执行用时: 897ms, 内存消耗: 34600K, 提交时间: 2021-04-27 19:19:58

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const ll N=507;
ll n,q,h[N],d[N][N];
void init(){
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++){
		d[i][i]=0;
		for(int j=1;j<i;j++){
			if(h[i]>h[j]){
				d[j][i]=(i-j+1)*h[i];
			}
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=n-1;j>=1;j--){
			d[i][j]=min(d[i][j],d[i][j+1]);
		}
	}
}
bool check(ll p,ll x,ll z){
	if(d[p][x]<=z){
		return true;
	}
	else{
		return false;
	}
}
int main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		ll p,z;
		scanf("%lld%lld",&p,&z);
		h[p]=z;
	}
	init();
	while(q--){
		ll p,z;
		scanf("%lld%lld",&p,&z);
		ll l=p,r=n,res=p;
		while(l<=r){
			ll mid=(l+r)/2;
			if(check(p,mid,z)){
				l=mid+1;
				res=mid;
			}
			else{
				r=mid-1;
			}
		}
		printf("%lld\n",res);
	}
}

详情