[51nod 1201] [DP+사유] 정수 구분 [N을 여러 개의 서로 다른 정수의 합으로 나누어 구분수를 구한다]

전송문:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201
아이디어:
dp[i][j]는 i라는 수를 j개수로 나누는 경우수를 나타낸다.
dp[i][j] = dp[i - j][j] + dp[i - j][j - 1]
전자는 i-1을 j 개수로 나누고 j 개수가 +1인지 중복되지 않는지를 나타낸다
후자는 i-1을 j-1개수로 나누고 j-1개수를 모두 +1하고 1을 더하는 것을 나타낸다
일반 dp는 O(n^2)이지만 1+2+...+m=n, (1+m)*m=n*2, j는 sqrt(n*2)개만 훑어보면 된다.그래서 복잡도는 O(n*sqrt(n*2)
코드:

#include 
using  namespace  std;
#define mod 1000000007
template void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
const int N=5e4+10;

int  dp[N][351], n;

int  main(){
  read(n);
  dp[0][0] = 1;
  for(int i = 1; i < 350 ; i++){//i  
    for(int j = 0; j <= n ; j++){//  j
      if(j - i >= 0){
        dp[j][i] = (dp[j - i][i] + dp[j - i][i - 1]) % mod;
      }
    }
  }
  int ans = 0;
  for(int i = 1; i < 350; i++)
    ans = (ans + dp[n][i]) % mod;
  printf("%d
", ans);
  return 0;
}

설명:
1201 정수 분할
기준 시간 제한: 1초 공간 제한: 131072KB점수: 80난이도: 5급 알고리즘 문제
수장하다
관심을 가지다
N을 몇 개의 서로 다른 정수의 합으로 나누면 몇 가지 다른 구분 방식이 있습니까? 예를 들어 n=6, {6} {1,5} {2,4} {1,2,3}, 모두 4가지입니다.데이터가 비교적 크기 때문에 모드 10^9+7의 결과를 출력하면 된다.
Input

  1  N(1 <= N <= 50000)。

Output

       Mod 10^9 + 7。

Input 예

Output 예

[51nod 1201] [DP+사유] 정수 구분 [N을 여러 개의 서로 다른 정수의 합으로 나누어 구분수를 구한다]

좋은 웹페이지 즐겨찾기