정수 분해에 관한 귀속법과 모함수법

22588 단어 차례로 돌아가다
먼저 제목:
Ignatius and the Princess III Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later."feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:   N=a[1]+a[2]+a[3]+...+a[m];   a[i]>0,1<=m<=N; My question is how many different equations you can find for a given N. For example, assume N is 4, we can find:   4 = 4;   4 = 3 + 1;   4 = 2 + 2;   4 = 2 + 1 + 1;   4 = 1 + 1 + 1 + 1; so the result is 5 when N is 4. Note that "4 = 3 + 1"and "4 = 1 + 3"is the same in this problem. Now, you do it!"
  Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
  Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
  Sample Input
4 10 20 Sample Output
5 42 627
먼저 귀속법, 이해하기 쉽지만, 분명히, 시간 초과...
#include <iostream>

using namespace std;

int s(int a,int b)

{

    if(a==1||b==1) return 1;

    if(a<b) return s(a,a);

    if(a==b) return (s(a,b-1)+1);

    if(a>b) return (s(a,b-1)+s(a-b,b));

}

int main()

{

    int n;

    while(cin>>n)

        cout<<s(n,n)<<endl;

    return 0;

}

그리고 모함수법:
모함수는 다항식의 곱셈에 세워진 것으로 먼저 이해해야 한다(1+X+X^2+X^3...)*(1+X^2+X^4+X^6......)*(1+X^3+X^6+X^9......).......얻은 aX^n, a는 n을 모으는 방법수입니다.모함수의 핵심은 삼중순환이다. 그 중에서 모함수에 관한 문제는 세 가지가 있다. 하나, 둘, 셋, 넷, 다섯...이렇게 +1,+1의, 그리고 수량에 제한이 없습니다. 예를 들어 정수 분할;2: 수량에 제한이 없지만 모든 수는 별도로 제시됩니다. 예를 들어 Square Coins.세 번째는 수는 따로 주고 수량을 제한하며 수량도 따로 준다.
먼저 가장 간단한 첫 번째 상황을 이야기한다.
정수 분할은 더 이상 제목을 주지 않는다.
 1 #include<iostream>

 2 using namespace std;

 3 int a[125],b[125];

 4 int main()

 5 {

 6     int i,j,k,n;

 7     for(i=0;i<=120;i++)

 8         a[i]=b[i]=1;

 9     for(i=2;i<=120;i++)

10     {

11         for(j=i;j<=120;j+=i)

12            for(k=0;k+j<=120;k++)

13                 b[j+k]+=a[k];

14         for(j=0;j<=120;j++)

15             a[j]=b[j];

16     }

17     while(cin>>n)

18         cout<<a[n]<<endl;

19     return 0;

20 }

다른 방법이지만 개인적으로 첫 번째가 비교적 좋다고 생각한다.
#include<iostream>

using namespace std;



#define M 200



int c1[M],c2[M];



int main()

{

    int n;

    while(cin>>n)

    {

        memset(c1,0,sizeof(c1));

        memset(c2,0,sizeof(c2));

        c1[0]=1;

        int j,i,k;

        for(i=1;i<=n;i++)

        {

            for(j=0;j<=n;j++)

                for(k=0;k+j<=n;k+=i)

                    c2[k+j]=c2[k+j]+c1[j];

            for(j=0;j<=n;j++)

                c1[j]=c2[j];

             memset(c2,0,sizeof(c2));

        }

        cout<<c1[n]<<endl;

    }

    return 0;

}         // 。。。。。。

물론 첫 번째는 가장 작은 데이터가 1이어야 한다는 한계가 있다. 왜냐하면:
for(i=0;i<=120;i++)        a[i]=b[i]=1;
만약 1이 아니라면 가장 작은 그 수로 바꾸어라.
이후의 삼중 순환의 첫 번째 중은 2부터 시작되지만 초기화할 필요도 없고 0을 분명히 할 필요도 없다.
첫 번째 코드의 삼중 순환은 다음과 같습니다.
i는 제 i의 괄호를 가리키고, j는 제 i의 괄호에 곱한 지수가 j의 항목을 가리키며, k는 지수가 k를 가리킨다.
다음은 두 번째 중 가능: 개수를 제한하지 않지만 모든 수는 제목이 따로 주는 것이지 +1+1+1이 아니다.
제목:
D - Square Coins Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 1398 Description
People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland. There are four combinations of coins to pay ten credits:
ten 1-credit coins, one 4-credit coin and six 1-credit coins, two 4-credit coins and two 1-credit coins, and one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
  Input
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.
  Output
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.
  Sample Input
2 10 30 0 Sample Output
1 4 27
 
분석: 우선 동전은 각각 1, 4, 9, 16...즉 n^2, 제목이 제시한 수량은 <=289이기 때문에 먼저 하나의 수조를 설정한다. c[17]={1,4,9,16,25,36,49,64,8110012144169164696252526289};
첫 번째 중순환은 i번째 괄호, 즉 동전 하나를 추가할 때마다 증가하는 멱수이기 때문에 for(l=1, k=c[l];l<17;l++, k=c[l])로 바꾸면 동전 하나를 늘릴 때마다 c[l]가 증가한다.
나머지는 변경되지 않으며 코드는 다음과 같습니다.
  
 1 #include <iostream>

 2 #include <stdio.h>

 3 using namespace std;

 4 int a[300],b[300];

 5 int main()

 6 {

 7     int i,j,k,l,c[17]={1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289},n;

 8     for(i=0;i<=300;i++)

 9        a[i]=b[i]=1;

10     for(l=1,k=c[l];l<17;l++,k=c[l])

11     {

12       for(j=k;j<=300;j+=k)

13          for(i=0;i+j<=300;i++)

14                b[i+j]+=a[i];

15       for(i=0;i<=300;i++)

16               a[i]=b[i];

17 

18     }

19 while(cin>>n,n)

20    cout<<a[n]<<endl;

21  return 0;

22 }

제출할 때 디스플레이는 15MS를 사용했지만 다른 방법은 0MS입니다.
다음과 같습니다.
  
 1 #include<stdio.h>

 2 #define max 310

 3 int main()

 4 {

 5     int coin[17] = {1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};

 6     int n,i,j,k, an[max], bn[max];

 7     while(scanf("%d", &n) && n)

 8     {

 9         for(i = 0; i <= n; i ++)

10         {

11             an[i] = 1;

12             bn[i] = 0;

13         }

14         for(j = 1; j < 17; j ++)

15         {

16             for(i = 0; i <= n; i ++)

17                 for(k = 0; k + i <= n; k += coin[j])

18                     bn[k + i] += an[i];

19             for(i = 0; i <= n; i ++)

20             {

21                 an[i] = bn[i];

22                 bn[i] = 0;

23             }

24         }

25         printf("%d
", an[n]);

26     }

27     return 0;

28 }

그러나 이것은 첫 번째 상황의 코드와 약간 비슷하다. 바로bn[i]이 끊임없이 0을 제거해야 한다는 것이다.
첫 번째 중순환은 여전히 두 번째 괄호(17만), 두 번째 중순환은 지수 i, 세 번째 중순환은 두 번째 괄호 안의 지수 k로 내가 쓴 코드의 두 번째와 세 번째 순서와 상반된다.
세 번째 상황:
제목:
C - 수강신청 시간(제목 수정, 문제 주의) Crawling in process...Crawling failed Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 2079 Description
또 수강신청 시간이 왔다. xhd는 수강신청표를 보고 멍하니 있다. 다음 학기를 좀 편하게 하기 위해 n학점을 배우는 데 모두 몇 개의 조합이 있는지 알고 싶다.네가 그를 좀 도와줘.(xhd는 같은 학점의 수업이 다르다고 생각한다)
  Input
입력 데이터의 첫 줄은 데이터 T로 T그룹 데이터가 있음을 나타냅니다.각 그룹의 데이터의 첫 줄은 두 개의 정수 n(1<=n<=40), k(1<=k<=8)이다.이어서 k행이 있고 줄마다 두 개의 정수 a(1<=a<=8), b(1<=b<=10)가 있으며 학점이 a인 과목은 b문임을 나타낸다.
  Output
각 그룹의 입력 데이터에 대해 하나의 정수를 출력하면 n학점을 배우는 조합수를 나타낸다.
  Sample Input
2 2 2 1 2 2 1 40 8 1 1 2 2 3 2 4 2 5 8 6 9 7 6 8 8 Sample Output
2 445
코드:
#include <iostream>

#include <stdio.h>

using namespace std;

int c1[645],c2[645];

int n,k,a[9],b[9],i;

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        cin>>n>>k;

        for(i=1;i<=k;i++)

            scanf("%d%d",&a[i],&b[i]);

        for(i=0;i<=n;i++)

            c1[i]=c2[i]=0;

        c1[0]=1;

        for(i=1;i<=k;i++)

        {

            for(int j=0;j<=n;j++)

                for(int l=0;l+j<=n&&l<=a[i]*b[i];l=l+a[i])

                c2[j+l]+=c1[j];

            for(int j=0;j<=n;j++)

                c1[j]=c2[j],c2[j]=0;

        }

        cout<<c1[n]<<endl;

    }

    return 0;

}

그래서 그 코드 템플릿을 사용하는 것이 좋다(첫 번째 상황과 두 번째 상황의 두 번째 방법).
이곳의 첫 번째 순환 중: i이중순환은 변하지 않는다. 제3중순환은 두 번째 기초 아래에 하나의 제한 조건이 추가되었다. l<=a[i]*b[i], 즉 수량의 제한이다.
자, 모함수는 여기까지 하고~~~~~ 오늘 풀었던 문제~~~ 내일 계속~\(≥≤)/~랄라
컴퓨팅 n!소요되는 시간 얻기
게임 패드에 유니티 파티 대화 장면의 메시지를 보내는 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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