p 정수 구분 문제--03: 복잡한 정수 구분 문제

정수 구분: 이 좋은 문제: 1.n을 약간의 정수의 합으로 나누는 구분수.　　2. n을 k개의 정수의 합으로 나누는 구분수.　　3. n을 최대 수가 k를 초과하지 않는 수로 나누다.　　4. n을 약간의 기정 정수의 합으로 나누는 구분수.　　5. n을 약간의 서로 다른 정수의 합으로 나누는 구분수.

1. 여러 정수로 나누면 같을 수 있다
dp[i][j]를 설정하여 i를 j보다 크지 않은 구분수로 나누기
(1) i일 때 i는 i보다 큰 수로 나눌 수 없기 때문에 dp[i][j]=dp[i][i];
(2) i>j일 경우 구분에 j가 함유되어 있는지 여부에 따라 두 가지 상황으로 나눌 수 있다.
만약 구분에 j가 포함된다면 구분 방안의 수는 dp[i-j][j]이다.
만약에 획분수에 j가 없다면 i를 j-1보다 크지 않은 획수로 나누는 것과 같다. dp[i][j-1]이다.
그래서 i>j일 때 dp[i][j]=dp[i-j][j]+dp[i][j-1];
(3) i=j일 때도 두 가지 상황으로 나뉜다.
만약 구분에 j가 한 가지 상황만 포함되어 있다면,
만약 구분에 j가 포함되지 않는다면 i를 j-1보다 크지 않은 구분수로 나누는 것과 같다.
이때 dp[i][j]=1+dp[i][j-1].
2. 정정수로 나누면 반드시 달라야 한다
dp[i][j]를 설정하여 i를 j를 초과하지 않는 서로 다른 정수로 구분하는 수
(1) i일 때 i는 i보다 큰 수로 나눌 수 없기 때문에 dp[i][j]=dp[i][i];
(2) i>j일 경우 구분에 j가 함유되어 있는지 여부에 따라 두 가지 상황으로 나눌 수 있다.
만약에 구분에 j가 포함된다면 나머지 구분 중 가장 큰 것은 j-1이고 방안 수는 dp[i-j][j-1]이다.
만약 구분에 j가 포함되지 않는다면 i를 j-1보다 크지 않은 구분수로 나누는 것과 같고 dp[i][j-1]이다.
그래서 i>j일 때 dp[i][j]=dp[i-j][j-1]+dp[i][j-1];
(3) i=j일 경우
만약 구분에 j가 함유되어 있다면 단지 하나의 상황일 뿐이다.
만약 구분에 j가 포함되지 않는다면 i를 j-1보다 크지 않은 구분수로 나누는 것과 같다.
이때 dp[i][j]=1+dp[i][j-1].

n을 k개의 정수로 나누는 수
dp[i][j]를 설정하여 i를 j개의 정수로 나누는 구분수를 설정합니다.
(1)i는 발생할 수 없는 상황으로 dp[i][j]=0;
(2) 만약에 i=j라면 i는 i개 1의 합으로 나눌 수 있고 dp[i][j]=1;
(3) i>j의 경우 구분수에 1이 포함되어 있는지 여부에 따라 두 종류로 나눌 수 있다.
만약 획분수에 1이 함유되어 있다면'절변법'을 사용하여 j개의 구분을 각각 1로 잘라낼 수 있다.
문제를 i-j의 j-1개 구분수로 바꾸어 dp[i-j][j-1]로 한다.
구분에 1이 포함되지 않으면 '절단법' 을 사용하여 j개의 구분수의 맨 아래 수를 절단합니다.
제목을 i-j의 j개 구분수로 바꾸어 dp[i-j][j]로 한다.그래서 i>j시 dp[i][j]=dp[i-j][j-1]+dp[i-j][j].

n을 약간의 정기수의 합으로 나누는 구분수

f[i][j]를 j개의 홀수의 합으로 나누는 구분수로 설정하고, g[i][j]는 i를 j개의 짝수의 합으로 나누는 구분수로 한다.
절단법을 사용하여 g[i][j]의 j개 구분을 모두 1로 나누면 f[i-j][j]를 얻을 수 있기 때문에
g[i][j] = f[i-j][j].
f[i][j]에는 1을 포함하는 구분 방안과 1을 포함하지 않는 구분 방안이 있다.1을 포함하는 구분 방안에 대해 1의 구분을 제외하고'i-1을 j-1의 홀수의 합으로 나누는 구분수', 즉 f[i-1][j-1]로 전환할 수 있다.1이 포함되지 않는 구분 방안에 대해 절단법으로 j개의 구분을 하나하나 1을 제거하고'i-j를 j개의 짝수의 합으로 나누는 구분수', 즉 g[i-j][j]로 전환할 수 있다.
그래서 f[i][j]=f[i-1][j-1]+g[i-j][j].
f[n][0]+f[n][1]+...+f[n][n]는 n을 약간의 홀수로 나누는 구분수로 문제 4의 답안이다.
다른 항목:
정수를 연속 양의 합으로 나누기
예를 들어 15는 4가지 연속 정수를 더한 형식으로 나눌 수 있다. 15 7 8 4 5 6 1 2 3 4 5는 먼저 일반적인 형식을 고려하고 n을 정정수로 하고 x를 구분한 후 가장 작은 정수로 한다. 만약에 n이 구분이 있다면 결과는 x이다. 만약에 두 가지 구분이 있다면 x와 x, x+1이다. 만약에 i가지 구분이 있다면 바로 x이다.
x ;
x 、x + 1 ;
x、 x + 1、 x + 2 、... ;
x、 x + 1、 x + 2、 ... 、 x + i - 1;모든 결과를 더하면 하나의 공식 (i * x + i * (i - 1)/2) = n, i는 현재 구분된 정수 개수이다.조건을 만족시키는 구분은 x를 정수로 하는 모든 상황이다.전례대로
i=1시, x=15;
i=2시, x=7;
i=3시, x=4;
i=4시, x=4/9;(x는 정수가 아니기 때문에 15는 4개의 정수로 나눌 수 없다)
i=5시, x=1;
i = 6시 x <1;(그래서 i는 최대 5)

자, 우리 문제를 봅시다

03: 복잡한 정수 구분 문제

총 시간 제한: 200ms 메모리 제한: 65536kB
묘사
정수 n을 일련의 정수의 합으로 나타낸다. n=n1+n2+...+nk, 그 중에서 n1>=n2>=>=nk>=1,k>=1.정수 n의 이런 표시를 정수 n의 구분이라고 한다.
입력
표준 입력은 몇 개의 테스트 데이터를 포함한다.각 그룹의 테스트 데이터는 두 개의 정수 N과 K를 포함하는 한 줄의 입력 데이터이다.
(0 < N <= 50, 0 < K <= N)
출력
각 그룹의 테스트 데이터에 대해 다음 세 줄 데이터를 출력합니다.
첫 번째 줄: N을 K개의 정수의 합으로 나누는 수
두 번째 줄: N은 여러 개의 서로 다른 정수의 합으로 나누어진 수
세 번째 줄: N은 몇 개의 기정 정수의 합으로 나누는 수
샘플 입력

5 2

샘플 출력

2
3
3

프롬프트
1행: 4+1, 3+2,
2행: 5, 4+1, 3+2
3행: 5, 1+1+3, 1+1+1+1+1

#include 
#include 
#include 
#include 
#include 

using namespace std;

int main()
{
    int n, k;
    while( cin >> n >> k )
    {
        int num[n+1][n+1];             //    n  k   dp  ;
        int num1[n+1][n+1];            //    n         dp  ;
        int g[55][55], f[55][55];      // g     dp  ， f     dp  ;
        int i, j;
                                    //    ;
        for( i=0; i<=n; i++ )
        {
            for( j=0; j<=n; j++ )
            {
                num[i][j] = num1[i][j] = f[i][j] = g[i][j] = 0;
            }
        }
                                    //            。
        for( i=1; i<=n; i++)
        {
            for( j=1; j<=n; j++)
            {
                if( i < j )
                {
                    num[i][j] = 0;
                    num1[i][j] = num1[i][j-1];
                }
                if( i == j )
                {
                    num[i][j] = 1;
                    num1[i][j] = 1 + num1[i][j-1];
                }
                if( i > j )
                {
                    num[i][j] = num[i-1][j-1] + num[i-j][j];
                    num1[i][j] = num1[i-j][j-1] + num1[i][j-1];
                }
            }
        }
                                 //        ，       ,        ;
        f[0][0]=1; g[0][0]=1;
        for( i=1; i<=n; i++ )
        {
            for( j=1; j<=i; j++)
            {
                g[i][j] = f[i-j][j];
                f[i][j] = f[i-1][j-1] + g[i-j][j];

            }
        }

        cout << num[n][k] <

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

최대 상승 하위 시퀀스(경로 인쇄)

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

p 정수 구분 문제--03: 복잡한 정수 구분 문제

자, 우리 문제를 봅시다

03: 복잡한 정수 구분 문제

좋은 웹페이지 즐겨찾기