167 条题解
-
4
琀予 LV 8 @ 2017-10-15 11:32:29
根据题意，守望者要在最短时间走最多的路程，而每秒有三种方法：休息（魔法恢复4），跑步（移动十七米），闪烁法术（花费10魔法，移动60米）。可以得到如下信息：
1.休息和闪烁魔法是有关联的（要不然还不如不休息）。
2.有魔法的情况下，尽量使用闪烁魔法（因为闪烁法术移动最远）。
3.在魔法不够的情况下，对休息（等待魔法恢复使用闪烁法术）还是跑步进行选择。
为了理清信息，不妨将跑步和使用闪烁法术分开处理。
设想：
1.如果守望者不会跑步，即第i秒的能到达最大距离为f[i],则：
f[i]={f[i-1]+60 当m（魔法）>=10时，同时m=m-10
f[i-1] 当m<10时，同时m=m+4
通过这样一个预处理，解决了闪烁法术的使用。
2.把跑步的情况加入，则：
f[i]=MAX(f[i],f[i-1]+17) (注意：令f[0]=0）
如此,得到了解决问题的递推式.当ft<S时，输出“No”及f[t]值，否则，就输出“Yes”及最快的离岛时间i。
综合上述分析，具体实现步骤如下：
1.读入数据M，S，T。
2.计算只使用闪烁法术时的每秒最大距离。
3.计算加入只使用跑步时的每秒最大距离，如果在某时刻刚好离岛，则输出离岛时间，结束。
4.如果没有离岛，输出最远距离，结束。
#include<iostream>
using namespace std;
long long m,s,t,i,f[500005];
int main()
{
cin>>m>>s>>t;
for(i=1;i<=t;i++)//循环时间
{
if(m>9)
{
f[i]=f[i-1]+60;
m-=10; //闪现
}
else
{
f[i]=f[i-1];
m+=4; //回蓝
}
}
for(i=1;i<=t;i++)
{
if(f[i]<f[i-1]+17) f[i]=f[i-1]+17;//判断跑步
if(f[i]>=s)
{
cout<<"Yes"<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<"No"<<endl<<f[t]<<endl;
return 0;
} -
4
无数组无循环
#include<bits/stdc++.h> using namespace std; int m,s,t; int main() { //freopen("escape.in","r",stdin); //freopen("escape.out","w",stdout); int t0=0; int sum=0; scanf("%d%d%d",&m,&s,&t); int a=m/10; if(60*a>=s&&a<=t) { printf("Yes\n"); if(s%60==0) printf("%d\n",s/60); else printf("%d\n",s/60+1); return 0; } if(t<=a) { printf("No\n%d\n",60*t); return 0; } m=m-10*a; m=m/2*2; /* if((m==2||m==3||m==4||m==5)&&t>=a+3) { t=t-2; t0=t0+2; a=a+1; m=0; } if((m==6||m==7||m==8||m==9)&&t>=a+2) { t=t-1; t0=t0+1; a=a+1; m=0; }*/ if((m==2||m==4)&&t>=a+3) { t=t-2; t0=t0+2; a=a+1; m=m-2; } if((m==6||m==8)&&t>=a+2) { t=t-1; t0=t0+1; a=a+1; m=m-6; } if(60*a>=s&&a<=t) { printf("Yes\n"); if(s%60==0) printf("%d\n",s/60+t0); else printf("%d\n",s/60+1+t0); return 0; } if(m==2&&t>=a+3) { t=t-2; t0=t0+2; a=a+1; m=0; } if(m==6&&t>=a+2) { t=t-1; t0=t0+1; a=a+1; m=0; } if(60*a>=s&&a<=t) { printf("Yes\n"); if(s%60==0) printf("%d\n",s/60+t0); else printf("%d\n",s/60+1+t0); return 0; } t=t-a; t0=t0+a; sum=60*a; int smax=sum; int t1=t/7,t2=t-t1*7; smax=smax+t1*120+t2*17; if(smax<s) { printf("No\n%d\n",smax); return 0; } a=(s-sum)/120; int b; if(s-sum-a*120%17==0) b=(s-sum-a*120)/17; else b=(s-sum-a*120)/17+1; if(b>=7) { a=a+1; b=0; } t0=t0+a*7+b; printf("Yes\n%d\n",t0); return 0; } -
1
aph。 (chenqianrong) LV 10 @ 2021-08-20 16:55:55
#include<bits/stdc++.h> using namespace std; int main() { int quantity,s,time; cin>>quantity>>s>>time; int s1=0,s2=0,time1=time; while(s>s1 && time>0) { s1+=17; if(quantity>=10){ s2+=60; quantity-=10; } else quantity+=4; s1=max(s1,s2); time--; } if(s1<s) cout<<"No"<<"\n"<<s1; else cout<<"Yes"<<"\n"<<time1-time; return 0; } -
1
#根据题意，守望者要在最短时间走最多的路程，而每秒有三种决策
##我们不妨将跑步和使用闪烁法术分开处理
###上代码
#include <cstdio> #include <algorithm> using namespace std; int dp[300001]; int main(){ int m,s,t; scanf("%d%d%d",&m,&s,&t); for(int i=1;i<=t;i++){//处理闪烁法术 if(m>=10)dp[i]=dp[i-1]+60,m-=10;//如果能用，就用 else dp[i]=dp[i-1],m+=4;//否则休息 } for(int i=1;i<=t;i++){dp[i]=max(dp[i],dp[i-1]+17);//处理跑步，dp[i]为使用法术和跑步的最大值（最优） if(dp[i]>=s){printf("Yes\n%d",i);return 0;}//如果超过了距离s，就成功了，输出yes }printf("No\n%d",dp[t]);//没成功，输出no return 0; } -
1
//远离DP
var m,s,t,time,run,magic:longint;
function find_max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;
begin
readln(m,s,t);
for time:=1 to t do
begin
if m>=10 then
begin
magic:=magic+60;
m:=m-10;
end
else m:=m+4;
run:=run+17;
run:=find_max(run,magic);
if run>=s then
begin
writeln('Yes');
writeln(time);
close(input);
close(output);
halt;
end;
end;
writeln('No');
writeln(run);
end. -
1
#include<iostream>//1172
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int m,n,s,ans,t,a[10001],b[10001],f[1000001];
bool flag;
int main()
{
cin>>m>>s>>t;
for (int i=1;i<=t;i++)
{
if (m>=10)
{
f[i]=f[i-1]+60;
m=m-10;
}
else
{
f[i]=f[i-1];
m+=4;
}
}
for (int i=1;i<=t;i++)
f[i]=max(f[i],f[i-1]+17);
for (int i=1;i<=t;i++)
{
if (f[i]>=s)
{
ans=i;
flag=true;
break;
}
if (i==t&&f[i]<s)
{
ans=f[i];
flag=false;
break;
}
}
if (flag==true)
cout<<"Yes"<<endl<<ans<<endl;
else
cout<<"No"<<endl<<ans<<endl;
return 0;
} -
1
#include<iostream>//1172
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int m,s,t,x,y,i;
int main()
{
cin>>m>>s>>t;
for(int i=1;i<=t;i++)
{
x+=17;
if(m>=10)
{
m-=10;
y+=60;
}
else
m+=4;
if(x<y)
x=y;
if(x>=s)
{
cout<<"Yes"<<endl<<i;
return 0;
}
}
cout<<"No"<<endl<<x;
return 0;
} -
1
dp解法
不可能把刷闪现和跑放在一起处理，所以分开两个循环做
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int magic,s,t,ans;
bool flag=false;
int f[300001];int main()
{
cin>>magic>>s>>t;for (int i=1;i<=t;i++){ //这一段纯粹刷闪现，有魔法就闪，没有就停下来补
if (magic>=10){
f[i]=f[i-1]+60;
magic-=10;
}else{
f[i]=f[i-1];
magic+=4;
}
}for (int i=1;i<=t;i++){ //利用跑步，确定最优解
f[i]=max(f[i],f[i-1]+17);
}for (int i=1;i<=t;i++){ //这后面的都是求解，没什么用
if (f[i]>=s){
ans=i;
flag=true;
break;}
if (i==t && f[i]<s){
ans=f[i];
flag=false;
}
}if (flag){
cout<<"Yes"<<endl<<ans<<endl;
}else{
cout<<"No"<<endl<<ans<<endl;
}
}
``` -
0
CCF书上有一模一样的题目
#include<iostream> #include<cstring> using namespace std; #define MAXN 300010 int main(){ int m,s,t,i; int f[MAXN]; cin>>m>>s>>t; f[0]=0; for(int i=1;i<=t;i++){//计算只用闪烁法术时的每秒最大距离 if(m>9)f[i]=f[i-1]+60,m-=10; else f[i]=f[i-1],m+=4; } for(int i=1;i<=t;i++){//计算加入跑步选择时的每秒最大距离 if(f[i]<f[i-1]+17)f[i]=f[i-1]+17; if(f[i]>=s){//刚好离岛 cout<<"Yes"<<endl<<i;return 0; } } cout<<"No"<<endl<<f[t];//不能离岛 return 0; } -
0
RP++ (贪吃蛇) LV 8 @ 2021-02-25 15:46:21
#include<bits/stdc++.h> using namespace std; int m,s,t,now=0; int main() { cin>>m>>s>>t; int s1=0,s2=0; for(int i=1;i<=t;i++) { s1+=17; if(m>=10) {s2+=60; m-=10; } else m+=4; if(s2>s1) s1=s2; if(s1>s) { cout<<"Yes"<<endl<<i<<endl; return 0; } } cout<<"No"<<endl<<s1<<endl; } -
0
/*此题dp，守望者有3个决策*/ #include<iostream> using namespace std; int m,s,t; int f[300005]; int main() { cin>>m>>s>>t; f[0]=0;//初始化 for (int i=1;i<=t;i++) { if (m>=10) {f[i]=f[i-1]+60;/*m>=10是表前一阶段+60*/m-=10;} //if (m<10) {f[i]=f[i-1]; m+=4;}阶段1s内只能有一个决策，用else； else {f[i]=f[i-1]; m+=4;} //守望者休息，恢复能量 } for (int i=1;i<=t;i++) { f[i]=max(f[i],f[i-1]+17);//DP if(f[i]>=s) {cout<<"Yes"<<endl<<i; return 0;} } cout<<"No"<<endl<<f[t]; return 0; } -
0
zhanglingran@163.com LV 7 @ 2018-04-20 21:54:52
**直接维护两个变量 x 和 y ,分别表示魔法值>=10 时候闪烁的距离x 和跑的距离y
**每秒判断 x 和 y 的大小。若x >= y 就将y 的值更新为x
**每秒判断 y 的大小和 S的差距，若T内能达到 y>=S,则输出yes和i;否则直接输出y的值
#include <iostream>
#include <cstdio>
#include <functional>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#include <utility>
#include <cstdlib>
#include <cmath>#define LL long long
#define MAX_N 110
#define INF 0x3f3f3f3f
using namespace std;int M,S ,T;
int main()
{
cin >> M >> S >> T;
int x = 0,y = 0;for(int i = 1;i <= T;i++){
if( M >= 10 ){
x+=60;
M-=10;
} else {
x = x;
M+=4;
}
y+=17;
if(x >= y){
y = x;
}
if(y >= S){
cout << "Yes"<< endl;
cout << i << endl;
return 0;
}
}cout << "No" << endl;
cout << y << endl;
return 0;
} -
0
#include<fstream>
#include<algorithm>
using namespace std;
int main()
{
int m,s,t;
scanf("%d%d%d",&m,&s,&t);
int a=0,b=0;
for(int i=1;i<=t;i++)
{
a+=17;//跑步
if(m>=10) //R闪
{
b+=60;
m-=10;
}
else //break
{
m+=4;
}
if (a<b) a=b;//bigger
if (a>s)
{
printf("Yes\n%d\n",i);
return 0;
}
}
if(a<s)
{
printf("No\n%d\n",a);
return 0;
}
return 0;
} -
0
每步最优，远离DP
var m,s,t,time,run,magic:longint;
function find_max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;
begin
readln(m,s,t);
for time:=1 to t do
begin
if m>=10 then
begin
magic:=magic+60;
m:=m-10;
end
else m:=m+4;
run:=run+17;
run:=find_max(run,magic);
if run>=s then
begin
writeln('Yes');
writeln(time);
close(input);
close(output);
halt;
end;
end;
writeln('No');
writeln(run);
end. -
0
liuxinglin2660638656 LV 5 @ 2017-10-17 17:38:59
var
m,s,t,x,y,i:longint;
begin
readln(m,s,t);
for i:=1 to t do begin
x:=x+17;
if m>=10 then begin m:=m-10;y:=y+60;end
else m:=m+4;
if x<y then x:=y;
if x>=s then begin writeln('Yes');writeln(i);exit;end;
end;
writeln('No');writeln(x);
end. -
0
讲道理 这道题我一直不明觉厉
var
m,s,t,s1,t1:int64;
begin
readln(m,s,t);
s1:=s;
t1:=t;
while (t>0) and (s>0) do
begin
if m>=10 then
begin
m:=m-10;
t:=t-1;
s:=s-60;
end
else
if (m>=6) and (t>=2) and (s>17) then
begin
m:=m+4;
t:=t-1;
end
else
if (m<6) and (m>=2) and (t>=3) and (s>51) then
begin
t:=t-2;
m:=m+8;
end
else
if (m<2) and (t>=7) and (s>119) then
begin
t:=t-5;
m:=m+20;
end
else
begin
s:=s-17;
t:=t-1;
end;
end;
if s>0 then
begin
writeln('No');
writeln(s1-s);
end;
if s<=0 then
begin
writeln('Yes');
writeln(t1-t);
end;
end.
-
0
卡线Ac
测试数据 #0: Accepted, time = 968 ms, mem = 548 KiB, score = 10
测试数据 #1: Accepted, time = 1000 ms, mem = 548 KiB, score = 10
测试数据 #2: Accepted, time = 1000 ms, mem = 552 KiB, score = 10
测试数据 #3: Accepted, time = 1000 ms, mem = 552 KiB, score = 10
测试数据 #4: Accepted, time = 1000 ms, mem = 556 KiB, score = 10
测试数据 #5: Accepted, time = 1000 ms, mem = 552 KiB, score = 10
测试数据 #6: Accepted, time = 1000 ms, mem = 552 KiB, score = 10
测试数据 #7: Accepted, time = 1000 ms, mem = 548 KiB, score = 10
测试数据 #8: Accepted, time = 1000 ms, mem = 548 KiB, score = 10
测试数据 #9: Accepted, time = 1000 ms, mem = 548 KiB, score = 10
Accepted, time = 9968 ms, mem = 556 KiB, score = 100
```
#ifndef _DEBUG#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#include <fstream>
#include <cmath>
#include <Windows.h>
#include <iterator>
#include <set>
using namespace std;
#endif // _DEBUGint main() {
int m, s, t;
Sleep(985);
scanf("%d%d%d", &m, &s, &t);
int a=0, b=0,i;
for (i = 1; i <= t; i++) {
a += 17;
if (m >= 10) { b += 60; m -= 10; }
else { m += 4; }
if (a < b)a = b;
if (a > s) { printf("Yes\n%d\n", i); return 0; }}
if(a>s) { printf("Yes\n%d\n", i); return 0; }else { printf("No\n%d\n", a); return 0; }return 0;
}
```
琀予
LV 8
@ 2017-10-15 11:32:29
