hdu 1028

1495 단어 HDU
http://acm.hdu.edu.cn/showproblem.php?pid=1028
간단 한 배달 인 줄 알 았 는데 편지지 세 장 을 돌려 보 냈 는데 도 미 루 지 못 하고 결국 남 의 문제 해결 보고 서 를 보 니 매우 심오 하 다.잘 안 밀 려 요.
여기 남 의 것 좀 붙 여 주세요. 느낌 이 좋아요.
정수 n 의 모든 다른 구분 에서 최대 가산 n1 이 m 보다 크 지 않 은 구분 개 수 를 q (n, m) 로 기록 합 니 다.q (n, m) 의 다음 귀속 관 계 를 만 들 수 있 습 니 다.
     <1>q(n,m) = 1, n >= 1
          최대 가산 점 n1 이 1 보다 크 지 않 을 때 그 어떠한 정수 n 은 하나의 구분 형식 만 있 고 n = 1 + 1 + 1 +... + 1
     <2>q(n,m) = q(n,n), m >= n
          최대 가산 n1 은 실제 n 보다 크 면 안 됩 니 다.
     <3>q(n,n) = 1 + q(n,n - 1)
          정수 n 의 구분 은 n1 = n 의 구분 과 n1 < n - 1 의 구분 으로 구성 된다.
     <4>q(n,m) = q(n, m - 1) + q(n - m, m),n > m > 1
          정수 n 의 최대 가산 점 n1 이 m 보다 크 지 않 은 구분 은 n1 = m 의 구분 과 n1 < = m - 1 의 구분 으로 구성 된다.
#include <cstdio>

#include <iostream>

int f[120][120];

void init()

{

   int i,j;

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

   {

       for(j=1;j<=120;j++)

       {

           if(i==1||j==1)

           f[i][j]=1;

           else if(i<j)

           f[i][j]=f[i][i];

           else if(i==j)

           f[i][j]=1+f[i][j-1];

           else

           f[i][j]=f[i][j-1]+f[i-j][j];

       }

   }

}

int main()

{

   init();

   int n;

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

   {

       printf("%d
",f[n][n]); } return 0; }

좋은 웹페이지 즐겨찾기