POJ 2385(선형 DP)

3497 단어 dp

제목의 뜻


현재 두 그루의 나무가 있는데, 1~t 안에 한 그루의 나무에서 사과 한 개가 떨어진다.처음에는 첫 번째 나무 밑에서 매번 현재 나무에서 떨어진 사과를 받거나 체력점 1개를 들여 순식간에 다른 나무 아래로 옮겨 사과를 받는다.너는 모두 w개의 체력점을 가지고 있다.t, w, 매 분마다 사과가 떨어지는 상황을 정해서 최대 몇 개의 사과를 얻을 수 있는지 물어보세요.

분석하다.


상태는 dp[i][j]로 정의: 전 t분 동안 j개의 체력점을 소비한 상태에서 얻을 수 있는 최대 사과 수입니다.상태 이동 방정식 dp[i][j]=max(dp[i-1][j], dp[i-1][j-1])+(i분 동안 현재 나무 밑에서 사과가 떨어지는지 여부).현재 상태는 두 가지 제한 조건이 있는데, 하나는 시간이고, 다른 하나는 이동 횟수, 즉 소모하는 체력점이다.그래서 이 1분의 상황은 1분의 상황으로 옮길 수밖에 없다.만약 1분 전에 움직이지 않았다면 이 나무였을 것이다. 바로 dp[i-1][j]+현재 나무에서 사과가 떨어졌는지;만약에 1분 전에 다른 그루 수였다면 하나의 체력점을 소모해야 한다는 뜻이다. 그러면 지금이 j라면 1분 전에 j-1이었기 때문에 dp[i-1][j-1]이다.마지막 문제는 현재 어떤 나무인지 어떻게 판단하는가이다. 매번 한 그루의 나무에서 다른 그루로만 뛸 수 있기 때문에 찾은 법칙에 의하면 홀수가 몇 번 뛰면 돌아온다. 즉, 가장 처음에 첫 번째 나무, 그리고 짝수가 다른 그루이다.또 하나 주의해야 할 것은 경계 판단, 구체적으로 코드를 보는 것이다

코드

#include 
#include 
#include 
using namespace std;
int dp[1005][35];
int a[1005];
int main()
{
    int t, w;
    while (cin >> t >> w)
    {
        int p;
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= t; i++)
            cin >> a[i];
        for (int i = 1; i <= t; i++)
        {
            for (int j = 0; j<=w; j++)
            {
                //      
                if (j > 0)dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
                else dp[i][j] = dp[i - 1][j];
                if (j % 2 + 1 == a[i]) 
                    dp[i][j]++;
            }
        }
        int  ans = dp[t][0];
        for (int i = 1; i <= w; i++)
            ans = max(ans, dp[t][i]);
        cout << ans << endl;
    }
    return 0;
}
GIMP로 LGTM 이미지를 만들어 보세요!(python-fu)
[JPA] Chapter 4. 엔티티 매핑 1 - 객체-테이블

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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