2018 블루 브리지 컵 성 경기 B조 시뮬레이션 경기(5)J. 프로그램 설계: 정수 구분

1245 단어
제목 링크:https://nanti.jisuanke.com/t/25093
이것은 정수 구분 문제에 관한 문제이다. 이런 문제는 여러 가지 문법이 있고 매우 유연하다. 그러나 세심하게 생각해 보면 서로 다른 문법은 사실 모두 관련이 있다. 정수 구분의 대체적인 모든 문법을 알고 싶은 사람은 이 블로그를 보십시오. 정수 구분 총결산
이 문제는 n을 k개수보다 많지 않은 것으로 분해하는 문제이다. 먼저 우리는 dp[][]수조를 정의하면 dp[i][j]는 정수 i를 j개수보다 많지 않은 방안수로 나누는 것을 의미한다.이 문제에 대해 우리는 두 가지 상황으로 분해할 수 있다
1. 최대 수는 j
2. 최대 수가 j보다 작다
두 번째 상황에 대해 그의 구분 방안은 dp[i][j-1]로 i를 최대수가 j-1보다 크지 않은 방안수로 나누는 것을 의미한다. 즉, i를 최대수가 j보다 작으면 점수를 나누는 것이다.첫 번째 상황에 대해 최대수는 j와 같고 만족하는 구분 조건은 dp[i-j][j]이다. i-j를 j를 초과하지 않는 방안수로 나누고'+j'를 각 구분의 뒤에 놓으면 최대수가 j와 같은 방안수를 얻을 수 있다.
이 문제의 또 하나는 롱롱을 켜야 한다는 것이다.
AC 코드:
#include 
#include 
#include 
#define ll long long
using namespace std;
int main()
{
  int a,b;
  scanf("%d%d",&a,&b);
  ll dp[305][305];
  memset(dp,0,sizeof(dp));
  dp[0][0] = 1;
  if(a == 1 || b == 1){
    printf("1
"); return 0; } for(int i=0;i<=a;i++){ for(int j=1;j<=a;j++){ if(i >= j){ dp[i][j] = dp[i-j][j] + dp[i][j-1]; } else if(j > i){ dp[i][j] = dp[i][i]; } } } printf("%lld
",dp[a][b]); return 0; }

좋은 웹페이지 즐겨찾기