80pts,dp代码求调,玄关
查看原帖
80pts,dp代码求调,玄关
705296
miffy_123楼主2024/3/14 21:25
/*
by miffy_123
question: luogu P1095 [NOIP2007 普及组] 守望者的逃离
https://www.luogu.com.cn/problem/P1095
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2147483646
#define inf 9223372036854775806
#define pl putchar('\n');
ll m,s,t;//m:初始魔法值,s:距离, t:岛沉没的时间
ll f[300005][14];//f[i][j] 在第i秒时剩余j点魔法值能跑多远 
int main(){
    cin>>m>>s>>t;
	ll t1=0,sum=0;//t:尽可能先使用闪现能用多少秒 sum:尽可能先使用闪现能闪到哪里 
	while(m>10){
		m-=10;
		t1++;
		sum+=60;
		if(sum>=s){
			cout<<"Yes"<<endl<<t1;
			return 0;
		}
		if(t1==t){
			cout<<"No"<<endl<<sum;
			return 0;
		}
	}
	memset(f,0xFF,sizeof(f));
	f[t1][m]=sum;
	for(int i=t1+1;i<=t;i++){
		for(int j=0;j<14;j++){
			f[i][j]=max(f[i][j],f[i-1][j]+17);
			if(j<4)f[i][j]=max(f[i][j],f[i-1][j+10]+60);
			else f[i][j]=max(f[i][j],f[i-1][j-4]);
			if(f[i][j]>=s){
				cout<<"Yes"<<endl<<i;
				return 0;
			}
		}
	}
	ll maxv=0;
	for(int j=0;j<14;j++){
		maxv=max(maxv,f[t][j]);
	}
	cout<<"No"<<endl<<maxv;
    return 0;
}


2024/3/14 21:25
加载中...