UPC 흑곰 강 건너기(기본 상태 이동)

2870 단어 동적 기획동적 기획 문제풀이
제목에서 알 수 있듯이 1~n의 범위 외에 두 개의 시작과 끝점이 존재한다. 0과 n+1이다. 그러나 2~n+1 범위 내의 상태는 모두 i-1과 i-2로 옮길 수 있기 때문에 이를 한 부분으로 나누고 0과 1은 이런 상태 이동 방식이 없기 때문에 다른 단독으로 해결하는 부분이다.
이 문제는 되돌아갔다가 되돌아오는 상황을 걱정할 필요가 없다. 왜냐하면 가장 좋은 해석에서 시작점 한쪽에서 끝점 저쪽으로 뛰는 것이 틀림없기 때문이다. 그렇지 않으면 헛되이 체력을 낭비하는 것이다.
n+1 상태를 제외하고 모든 상태는 현재 상태의 수치가 도약에 필요한 에너지 수치보다 작으면 안 된다는 것을 확인해야 한다. 그렇지 않으면 이 상태는 무의미하다. 왜냐하면 종점에 도달하기 전에 모든 행동 능력을 손실했기 때문이다.
즉 다음과 같은 생각이 든다.
흑곰이 0과 1에 있는 상태를 단독으로 판단점차로 흑곰이 2~n+1 상태에 있음
//#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define DETERMINATION main
#define lldin(a) scanf_s("%lld", &a)
#define println(a) printf("%lld
", a)
#define reset(a, b) memset(a, b, sizeof(a))
const int INF = 0x3f3f3f3f;
using namespace std;
const double PI = acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1000000007;
const int tool_const = 19991126;
const int tool_const2 = 2000;
inline ll lldcin()
{
    ll tmp = 0, si = 1;
    char c;
    c = getchar();
    while (c > '9' || c < '0')
    {
        if (c == '-')
            si = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        tmp = tmp * 10 + c - '0';
        c = getchar();
    }
    return si * tmp;
}
///Untersee Boot IXD2(1942)
/**Although there will be many obstructs ahead,
the desire for victory still fills you with determination..**/
/**Last Remote**/
ll a[65555],dp[65555],vis[65555];
int DETERMINATION()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    ll p, q;
    cin >> p >> q;
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[n + 1] = 0;// n+1            
    dp[0] = p;
    if (dp[0] < q)//      
    {
        cout << "NO" << endl;
        return 0;
    }
    vis[0] = true;
    dp[1] = dp[0] - q + a[1];
    if (dp[1] >= q)//            ，         
        vis[1] = true;
    for (int i = 2; i <= n+1; i++)
    {
        if (vis[i - 1] + vis[i - 2] == 0)//          
        {
            cout << "NO" << endl;
            return 0;
        }
        else if (vis[i - 1] && !vis[i - 2])
            dp[i] = a[i] - q + dp[i - 1];
        else if (vis[i - 2] && !vis[i - 1])
            dp[i] = a[i] - q + dp[i - 2];
        else
            dp[i] = max(dp[i - 2] + a[i] - q, dp[i - 1] + a[i] - q);
        if (dp[i] - q >= 0)//            ，         
            vis[i] = true;
    }
    cout << dp[n + 1] << endl;
    return 0;
}

μStyler
keepalived+nginx

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage