HDU1133 문제 해결(점진적 접근 방식)

HDU1133 문제 해결

제목의 뜻

m과 n은 표를 사러 간다. m은 50위안, n은 100위안이다. 몇 가지 표 사는 방식이 있는지 물어본다.

활용단어참조

이 문제를 풀기 전에 카틀란의 수가 무엇인지 전혀 몰랐다. 자신이 큰 수 dp를 썼으니 먼저 그 생각을 말해 보자.

void solve()
{
        dp[1][0][0]='1';dp[0][0][0]='0';
        for(int i=2;i<=200;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(i-j>j)
                {
                    continue;
                }
                BigAddBig(dp[j][i-j],dp[j-1][i-j],dp[j][i-j-1]);
            }
        }
}

dp[i][j]는 i개 50원, j개 100원을 뜻하는데 이때의 방안수는 분명히 dp[i][j]=dp[i-1][j]+dp[i][j-1]이다.그러나 이렇게 구한 최종 방안수는 사실상 모든 사람을 동일하게 보는 것이므로 주의해야 한다. 즉, 방안수를 구할 때 최종적으로 *fac(i)*fac(i-1)를 요구한다.

전체 코드

#include
#define MAXN 1000
using namespace std;
char fac[201][MAXN];
char dp[201][201][1005];
char ans1[100005],ans2[1000005];
int n,m;
void BigNumMultiSmall(char *a, char *b, int mul)
{
    //a    ，b     ，mul    
    int i, j, len;
    int a_int[2000] = { 0 }, b_int[1000] = { 0 };
    len = strlen(b);
    for (i = 0; i < len; i++)
        b_int[i] = b[len - 1 - i] - '0';
    for (i = 0; iif (a_int[i]>9)
        {
            a_int[i + 1] = a_int[i] / 10;
            a_int[i] = a_int[i] % 10;
        }
    }
    while (a_int[i])
    {
        a_int[i + 1] = a_int[i] / 10;
        a_int[i] = a_int[i] % 10;
        i++;
    }
    while (a_int[i - 1] == 0)
        i--;
    for (j = 0; j < i; j++)
        a[j] = a_int[i - j - 1] + '0';
    a[j] = '\0';
}
void BigMultiBig(char *a, char *b, char *c)
{
    int i, j, len1, len2, len;
    int a_int[2010] = { 0 }, b_int[1000] = { 0 }, c_int[1000] = { 0 };
    len1 = strlen(b);
    for (i = len1 - 1; i >= 0; i--)
        b_int[len1 - i - 1] = b[i] - '0';
    len2 = strlen(c);
    for (i = len2 - 1; i >= 0; i--)
        c_int[len2 - i - 1] = c[i] - '0';
    len = len1 + len2;
    for (i = 0; i < len1; i++)
    for (j = 0; j < len2; j++)
        a_int[i + j] += b_int[i] * c_int[j];
    for (i = 0; iif (a_int[i]>9)
    {
        a_int[i + 1] += a_int[i] / 10;
        a_int[i] = a_int[i] % 10;
    }
    while (a_int[len - 1] == 0)
        len--;
    for (i = 0; i < len; i++)
        a[i] = a_int[len - i - 1] + '0';
    a[i] = '\0';
    if (strlen(a) == 0)
        strcpy(a, "0");
}
void BigAddBig(char *a, char *b, char *c)
{
    //a    ，b,c   
    int a_int[1005] = { 0 }, b_int[1005] = { 0 }, c_int[1005] = { 0 };
    int len1, len2, len, i;
    len1 = strlen(b);
    len2 = strlen(c);
    for (i = 0; i < len1; i++)
        b_int[i] = b[len1 - 1 - i] - '0';
    for (i = 0; i1 - i] - '0';
    len = len1>len2 ? len1 : len2;
    for (i = 0; iif (a_int[i]>9)
        {
            a_int[i + 1] = a_int[i] / 10;
            a_int[i] = a_int[i] % 10;
        }
    }
    if (a_int[i] != 0)
        len++;
    while (!a_int[len - 1])
        len--;
    for (i = 0; i < len; i++)
        a[i] = a_int[len - 1 - i] + '0';
    a[i] = '\0';
}
void init()
{
    fac[0][0]='1';fac[1][0]='1';
    for(int i=2;i<=200;i++)
    {
        BigNumMultiSmall(fac[i],fac[i-1],i);
       // printf("%s
",fac[i]);
    }
}
void solve()
{
        dp[1][0][0]='1';dp[0][0][0]='0';
        for(int i=2;i<=200;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(i-j>j)
                {
                    continue;
                }
                BigAddBig(dp[j][i-j],dp[j-1][i-j],dp[j][i-j-1]);
            }
        }
}
int main()
{
    init();
    solve();
    int t=1;
    while(scanf("%d %d",&n,&m))
    {
        if((!n)&&(!m))
        {
            break;
        }
        BigMultiBig(ans1,fac[n],dp[n][m]);
        BigMultiBig(ans2,ans1,fac[m]);
        printf("Test #%d:
",t++);
        printf("%s
",ans2);
    }
}