ACM 트레이닝 방법 [단순 반복 + 기억화 검색]

제목

제목 분석

전체 코드

제목

제목 설명
자전거 선수는 훈련할 때 장소를 둘러싸고 N바퀴를 타야 한다.주어서 훈련을 효과적으로 할 수 있다. 한 번에 N을 모두 탈 수도 있고 몇 번으로 나누어 완성할 수도 있다. 그러나 매번 지난번에 탄 바퀴 수보다 많다. 그러면 한 번의 훈련을 완성하면 N바퀴를 탈 수 있고 여러 가지 훈련 방식이 있다.
샘플 입력
육
샘플 출력
사

제목 분석

예를 들어 N = 6시에는 다음과 같은 4가지 훈련 방안이 있습니다.
자세히 생각해 보면 이것은 간단한 귀속이다. 매번 전달되는 매개 변수는 이전에 선택한 값(이번에 선택한 값보다 작을 수 없음)과 현재 남은 사용 가능한 총량은 기억화 검색을 사용하지 않으면 데이터가 100까지 올라가는 것이 비교적 힘들기 때문에 분명히 기억화 검색을 사용해야 한다.

전체 코드

#include
#include
#include
#define maxn 500
using namespace std;
long long m[maxn][maxn];
bool vis[maxn][maxn];
int dd(int i, int n) {
    if (vis[i][n])
        return m[i][n];
    vis[i][n] = true;
    if (n == 0)
        return m[i][n] = 1;
    else if (i >= n)
        return m[i][n] = 0;
    else {
        for (int j = i + 1; j <= n; ++j) {
            m[i][n] += dd(j, n - j);
        }
        return m[i][n];
    }
}
int main() {
    int n;
    while (cin >> n) {
        memset(m, 0, sizeof(m));
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            dd(i, n - i);
        }
        for (int i = 1; i <= n; ++i)
                m[0][n] += m[i][n-i];
        cout << m[0][n] << endl;
    }
}