Vijos P1431 파수꾼 의 탈출 (동적 계획 + 욕심) (해결 되 지 않 음)

묘사 하 다.
악마 사냥꾼 유 디 안 은 야심 만만 하 다. 그 는 어둠 의 정령 을 배신 하고 바다 밑 에 숨 어 있 는 나 가족 을 이 끌 고 반란 을 기도 했다.파수꾼 은 유 디 안과 의 교전 에서 포위 공격 을 당 해 황폐 한 섬 에 갇 혔 다.유 디 안 은 파수꾼 을 죽 이기 위해 이 무인도 에 주문 을 걸 기 시작 했다. 이 섬 은 곧 가라앉 을 것 이다.그때 가 되면 섬의 모든 사람들 이 조난 을 당 할 것 이다.파수꾼 의 달리기 속 도 는 17m / s 로 이런 속도 로 는 무인도 에서 벗 어 날 수 없다.다행히 파수꾼 은 신 틸 레이 션 마법 을 가지 고 있어 1s 내 60m 를 이동 할 수 있 지만, 신 틸 레이 션 마법 을 사용 할 때마다 마법 치 를 10 포인트 소모 합 니 다.파수꾼 의 마법 치 회복 속 도 는 4 시 / s 로 제자리 휴식 상태 에 있 을 때 만 회복 할 수 있다.현재 파수꾼 의 마법 초기 값 M, 그 가 있 는 초기 위치 와 섬의 출구 사이 의 거리 S, 섬 이 침몰 한 시간 T 로 알려 져 있다.
당신 의 임 무 는 파수꾼 이 가장 짧 은 시간 안에 황량 한 섬 을 탈출 하 는 방법 을 계산 하 는 데 도움 을 주 는 프로그램 을 작성 합 니 다. 만약 탈출 하지 못 한다 면 수출 파수꾼 이 남 은 시간 에 갈 수 있 는 가장 먼 거 리 를 계산 합 니 다.주의: 파수꾼 의 달리기, 반 짝 임 또는 휴식 활동 은 모두 초 (s) 단위 이 고 매번 활동 의 지속 시간 은 정수 초 입 니 다.거리의 단 위 는 미터 (m) 다.
분석 하 다.
아니면 분석 에 착안 하여 이 문 제 를 해결 하 는 것 이 분명 하 다. 우리 의 결정 은 우리 가 매 초 에 달리 기 를 선택 하 는 것 이 냐, 아니면 마법 을 사용 하 는 것 이 냐, 아니면 마법 을 회복 하 는 것 이 냐 하 는 것 이다. 그 다음 에 우리 가 결정 하 는 전략 이 무엇 인지 알 아야 한다. 이것 은 바로 팬 이 뚜렷 하 다. 우리 의 전략 은 바로 '더 멀리 달 리 는 것' 이나 '사용 할 때 더 적다' 는 것 이다.이 두 가지 전략 이 같 을 까? 즉, 탈출 할 수 있다 면 반드시 작은 여 해도 가 침몰 하 는 시간 t. 예 를 들 어 탈출 할 때 t1 이다. 그러면 이 때 는 반드시 t1 시의 최대 이동 거리 x 이다. 그러면 우리 의 이 두 가지 상황 은 하나의 상태 와 결정 전략 으로 해결 할 수 있다.그러면 이 문 제 를 해결 하기 위해 우 리 는 하나의 상 태 를 정의 한다. 아까 의 분석 을 통 해 알 수 있 듯 이 우리 의 거리 x 는 반드시 상태 자체 이 고 시간 을 매개 변수 로 할 수 있다. 그래서 우 리 는 f [i] 가 'is 내 에서 이동 하 는 최대 거리' 라 고 정의 한다. 그러면 우리 의 전략 은 반드시 f [i] 를 최대 로 하 는 것 이다. 그러면 i 시간 에 마법 을 사용 할 수 있다 면...그러면 우 리 는 반드시 마법 을 사용 할 것 이다. 다른 두 가지 선택 을 어떻게 선택 하 느 냐 가 관건 이다. 이 럴 때 우 리 는 번 거 로 움 을 두려워 하지 않 고 상황 을 꼼꼼 히 살 펴 봐 야 한다.
우선, 우 리 는 가장 일반적인 상황 을 분석 합 니 다. 즉, 우 리 는 축력 과 사용 할 때 경계 에 직면 하지 않 습 니 다. 만약 에 우리 가 현재 의 법 력 치가 0 이 라면 우 리 는 축력 에서 사용 한 후에 4s 시간 이 필요 합 니 다. 이동 거 리 는 60 미터 입 니 다. 만약 에 그 동안 우 리 는 달리 기 를 선택 하면 68 미터 거 리 를 달 릴 것 입 니 다. 그러면 분명 합 니 다. 만약 에 우리 의 법 력 치가 0 이 라면...우 리 는 전혀 축력 을 선택 하지 않 을 것 이다!그러면 마찬가지 로 우리 의 법 력 치가 1 일 때 도 마찬가지 입 니 다. 우리 가 2 시 법 력 이 있 을 때 우 리 는 축력 부터 사용 까지 3s 가 필요 하고 이동 거 리 는 60m 입 니 다. 그 동안 달리 기 를 선택 하면 51m 가 이동 합 니 다. 그래서 법 력 치가 2 보다 크 면 10 보다 적 을 때 우 리 는 축력 을 선택 합 니 다. 그러나 축력 기간 에 경계 조건 에 이 르 렀 을 때의 판단 도 고려 해 야 합 니 다.즉, 힘 을 모 으 는 시간 안에 오지 않 고 마법 을 사용 하면 시간 이 다 떨 어 지면 분명히 수지 가 맞지 않 는 다. 또 다른 상황 은 우리 의 거리 가 60m 가 필요 하지 않 고 나 가면 우리 도 수지 가 맞지 않 는 다 는 것 이다.
자, 마지막 으로 이런 특수 한 상황 을 자세히 분석 해 보 겠 습 니 다. 첫 번 째, 축력 시간 내 에 오지 않 은 것 과 마법 을 사용 하면 시간 이 다 떨 어 집 니 다. 이런 상황 에서 우 리 는 매번 결정 사이 에 판단 을 추가 하여 남 은 시간 에 마법 을 다 사용 할 수 있 는 지, 두 번 째 는 선택 하기 전에 판단 을 추가 할 수 있 습 니 다.남 은 거리 달리기 용 으로 힘 을 모 으 고 마법 을 쓰 는 것 보다 적은 지 판단 하 는 조건 이다.우리 의 데이터 분석 을 통 해 몇 가지 상황 코드 를 다음 과 같이 나 누 었 다.

//
//  main.cpp
//     
//
//  Created by     on 16/1/20.
//  Copyright © 2016     . All rights reserved.
//
//
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    freopen("/Users/zhangjiatao/Desktop/input.txt","r",stdin);
    int m,s,t,f[500000],flag;
    flag=0;
    memset(f,0,sizeof(f));
    cin>>m>>s>>t;
    for(int i=1;i<=t;i++)
    {
        if(m>=10) f[i]=f[i-1]+60,m=m-10;
        else if(m>=6&&m<=9)
        {
            if(t-i<=1) f[i]=f[i-1]+17;
            else if(s-f[i-1]<=17) f[i]=f[i-1]+17;
            else f[i]=f[i-1],m+=4;
        }
        else if(m>=2&&m<=5)
        {
            if(t-i<=2) f[i]=f[i-1]+17;
            else if(s-f[i-1]<=34) f[i]=f[i-1]+17;
            else f[i]=f[i-1],m+=4;
        }
        else f[i]=f[i-1]+17;
        if(f[i]>=s)
        {
            cout<<"Yes"<<endl;
            cout<<i<<endl;
            //cout<<f[i]<<endl;
            flag=1;
            break;
        }
    }
    if(flag==0)
    {
        cout<<"No"<<endl;
        cout<<f[t]<<endl;
    }
    return 0;
}