167 条题解

  • 4
    @ 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
    @ 2017-08-07 11:20:37

    无数组无循环

    
    #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
    @ 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
    @ 2020-05-15 23:04:41

    #根据题意,守望者要在最短时间走最多的路程,而每秒有三种决策

    ##我们不妨将跑步和使用闪烁法术分开处理

    ###上代码

    #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
    @ 2017-11-04 20:36:59

    //远离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
    @ 2017-09-11 21:44:26

    #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
    @ 2017-09-10 15:03:05

    #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
    @ 2017-08-11 17:00:58

    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
    @ 2021-07-13 12:08:29

    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
    @ 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
    @ 2019-09-07 15:58:41

    这个贪心就行了吧

  • 0
    @ 2018-06-11 21:45:09
    /*此题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
    @ 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
    @ 2017-11-05 16:49:16

    #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
    @ 2017-11-03 21:08:11

    每步最优,远离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
    @ 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
    @ 2016-09-10 19:03:06

    简单贪心
    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
    @ 2016-09-03 16:44:00

    讲道理 这道题我一直不明觉厉

    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
    @ 2016-08-02 11:29:04

    卡线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 // _DEBUG

    int 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;
    }
    ```

  • 0
    @ 2016-07-17 20:22:41

    不能就最后1次比较跑的和使用魔法哪个快,不考虑前面跑的 至少要比较后两次啊!!!!!!
    (可证明,由于可能最后一次不能使用魔法,倒数第二次用魔法4s才走了60,普通走比不用魔法快,4s可走68,但2组魔法一起用一定比走快,所以是两次)
    否则第8个点过不去啊!
    后来写了个每次都比较魔法和走 就ac了

信息

ID
1431
难度
5
分类
动态规划 | 背包 点击显示
标签
递交数
6110
已通过
1899
通过率
31%
被复制
14
上传者