方法一：贪心算法
解题思路：每一秒 如果能量大于10的话，肯定优先闪烁，这样跑的远，如果能力不够的话，可以休息，浪费一秒恢复+4的能量，要么直接跑步一秒17米；2种方案进行pk，走的远的优先考虑，在继续考虑下一秒种的情况，如果走的距离，在t秒之前大于s则，可以成功跳出，否则的话，不可以跳出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
int m,s,t;// m代表初始能力值，s代表距离，t代表最长的下沉时间
int main()
{
cin>>m>>s>>t;
int i;
int s1=0;// 步行的累计距离
int s2=0; // 闪烁+休整的累计距离
for(i=1;i<=t;i++)
{
s1=s1+17;// 每秒走17米 方案1，单纯的步行
if(m>=10)
{
m=m-10;// 闪烁消耗10能力
s2=s2+60;
}
else
m=m+4;// 能力不够，也可以休息，积累能力，为了，更好的闪烁
if(s2>s1)
s1=s2;// 闪烁块的话，步行可以在闪烁的基础上，继续步行；步行快的话，说明能力不够，不能够闪烁，不需要更新
if(s1>=s)
{
cout<<"Yes"<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<"No"<<endl;
cout<<s1<<endl;
return 0;
}
|
方法2：动态规划法
解题思路：dp【i】=代表i秒钟闪烁的距离，要么闪烁，要么修正恢复体力计算每一秒钟的距离,然后在与步行进行pk，那个走的远，就选择那个进行下一秒dp[i]=max(dp[i],dp[i-1]+17); 闪烁完之后，可以步行，优先考虑闪烁。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
int dp[300005];
int m,s,t;// m代表初始能力值，s代表距离，t代表最长的下沉时间
int main()
{
cin>>m>>s>>t;
int i;
for(i=1;i<=t;i++)
{
if(m>=10) // 如果能量大于10，就闪烁，消化10，距离增加60，否则，就休息一秒
{
dp[i]=dp[i-1]+60;
m=m-10;
}
else
{
dp[i]=dp[i-1];// 距离不动，原地休息
m=m+4;
}
}
for(i=1;i<=t;i++)
{
if(dp[i]<dp[i-1]+17) // 闪烁与步行pk哦,两者取其较大者
{
dp[i]=dp[i-1]+17;
}
if(dp[i]>=s)
{
cout<<"Yes"<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<"No"<<endl<<dp[t]<<endl;
return 0;
}
|
