HDU 1028 정수 분화

HDU 1028 제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1028 제목: 정수 구분 사고: 상태 dp [i] [j] 는 숫자 를 i 로 표시 하고 가장 큰 구성 숫자 는 j 의 dp 값 이다.그리고 기억 화 된 검색 방법 으로 쓰 시 면 됩 니 다.원본 코드:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define LL long long
const int MAXN = 200;
LL dp[MAXN][MAXN];
void dfs(int u, int v)
{
    if(u == v){
        dp[u][v] = 1;
        return;
    }
    if(v == 1){
        dp[u][v] = 1;
        return;
    }
    if(dp[u][v] != 0)   return;
    for(int i = 1 ; i <= min(u - v, v) ; i++){
        dfs(u - v, i);
        dp[u][v] += dp[u - v][i];
    }
}
void init()
{
    memset(dp, 0, sizeof(dp));
    for(int i = 1 ; i < MAXN ; i++){
        for(int j = 1 ; j <= i ; j++)
            dfs(i, j);
    }
}
int main()
{
    init();
    int n;
    while(scanf("%d", &n) != EOF){
        LL ans = 0;
        for(int i = 1 ; i <= n ; i++)
            ans += dp[n][i];
        printf("%I64d
"
, ans); } return 0; }

좋은 웹페이지 즐겨찾기