POJ2385--Apple Catching

1409 단어
제목: Farmer John은 처음에 나무 1 아래에 서 있었다. 그는 나무 1과 나무 2 사이를 왕복으로 W번 이동할 수 있었다. 분당 한 번만 이동할 수 있고 분당 한 그루의 나무만 사과를 떨어뜨릴 수 있었다. 시간은 T분 안에 사과 몇 개를 얻을 수 있느냐고 물었다.
 
분석: 상태: dp[i][j]는 i분에 j회 이동한 애플의 수를 나타낸다.
상태 이동 방정식: dp[i][j]=max(dp[i-1][j], dp[i-1][j-1]), 그리고 현재 i분에 사과가 떨어진 나무 밑에 있는지 판단한다. 그렇다면 dp[i][j]++.
상태 이동 방정식에 대한 설명은 다음과 같다. i분에 얻을 수 있는 사과 수량은 i-1분에 나무 1과 나무 2에서 사과의 최대치를 얻는 것과 같다.j가 짝수이면 나무 1 아래, 홀수는 나무 2 아래에 있다.
코드:
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1111;

int a[maxn], dp[maxn][40];

int main() {
    int t, w;
    while(~scanf("%d%d", &t, &w)) {
        for(int i = 1; i <= t; i++)
            scanf("%d", &a[i]);
        if(a[1] == 1) {
            dp[1][0] = 1;
            dp[1][1] = 0;
        }
        else {
            dp[1][0] = 0;
            dp[1][1] = 1;
        }
        for(int i = 2; i <= t; i++) {
            for(int j = 0; j <= w; j++) {
                if(j == 0) dp[i][j] = dp[i-1][j] + a[i]%2;
                else {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
                    if(j%2+1 == a[i]) dp[i][j]++;
                }
            }
        }
        int ans = 0;
        for(int i = 0; i <= w; i++)
            ans = max(ans, dp[t][i]);
        printf("%d
", ans);

    }
    return 0;
}
A/B com Javascript 테스트 간소화
uva10564

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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