HDU 5366 The mook jong(DP)

1576 단어
제목: n개의 빈칸에 말뚝을 놓고, 말뚝 사이에 적어도 두 개의 빈칸을 두고, 모두 몇 가지 방법이 있는지 묻는다.
아이고.사실 나는 자신의 경기 코드를 말하는 것을 거절했다.dp잖아요.
저는 dp[i][j]로 하여금 i개의 빈칸을 표시하고 j개의 말뚝을 놓는 방법수입니다.
그리고 전이 방정식은 dp[i][j]=dp[i-3][j-1]+dp[i-4][j-1]+...+dp[1][j-1];
첫 번째 빈칸에 말뚝을 놓고 j-1개의 말뚝을 남기면 i-3개의 빈칸에 넣어야 한다는 뜻이다.
그리고 두 번째 빈칸은 말뚝을 놓고 나머지 j-1개의 말뚝은 i-4개의 빈칸에 넣고 마지막에 모두 합치면 된다.
인트가 터질 수 있으니 롱롱으로 하면 돼요.
#pragma warning(disable:4996)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#define LL long long
#define N 1010
using namespace std;

LL dp[65][22];
LL ans[65];

int main(){
    //init
    for (int i = 0; i < 22; i++)dp[1][i] = 0;
    for (int i = 0; i <= 60; i++)dp[i][1] = i;
    dp[1][1] = 1;
    for (int j = 2; j < 22; j++){

        for (int i = 2; i <= 60; i++){
            LL sum = 0;
            for (int k = i - 3; k >= 1; k--)sum += dp[k][j - 1];
            dp[i][j] = sum;
        }
    }
    for (int i = 1; i <= 60; i++){
        for (int j = 1; j < 22; j++){
            ans[i] += dp[i][j];
        }
    }
    int n;
    while (cin >> n){
        cout << ans[n] << endl;
    }
    return 0;
}

다음은 hack에서 본 대신의 코드(O O"...hack도 갈게요...)
dp[i]는 i개의 스페이스 바를 말뚝에 놓는 방법의 수를 나타낸다.
전이 방정식은 dp[i]=dp[i-1]+dp[i-3]+1이다.
이해는 첫 번째 칸에 말뚝 dp[i-1]를 놓지 않거나 첫 번째 칸에 말뚝 dp[i-3]를 놓거나 첫 번째 칸에만 말뚝을 놓는 것이다.
코드가 너무 간단해서, 여기서는 생략하였다.
로곡 P1002하수인dp 패스 수
[Python]Binary Search, 이진 탐색

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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