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

3057 단어 NUISTOJ
  • 제목
  • 제목 분석
  • 전체 코드

    • 제목


    제목 설명
    자전거 선수는 훈련할 때 장소를 둘러싸고 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;
    }
}
    백서 연습 두 갈래 나무의 재구성
    Resources.검증 BestPractices 로드 (1, 로드 및 제거)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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