구분수

2101 단어
도전문제
***************************************************************************************
주의는 초과하지 않는다
1. dp[i][j]=j의 i를 정의하는 구분 총수 j의 i 구분은 j가 고정된 의미를 나타내고 i는 1-i를 얻을 수 있다.
2. 추이 공식 dp[i][j]=dp[i][j-i]+dp[i-1][j];
3. 분류 토론:
      1.j>=i 시, dp[i][j]=dp[i-1][j](j의 i-1 구분은 현재 위치가 0을 취하는 모든 상황에 해당) + dp[i][j-i](현재 위치가 0을 취하지 않으면 하나하나를 1로 설정하고 나머지 j-i를 나눈다).
      2.j예제:
곽 언니는 요즘 심심해서 돌을 나누기 시작했다.곽 언니는 n개의 돌이 있는데, 그녀는 돌을 m더미로 나누려고 한다. 한 무더기에 적어도 한 개의 돌이 있는데, 그녀는 몇 가지 분법이 있는지 알고 싶다
설명 입력
  • 정수 2개, n과 m(m<=n<=20).

  • 출력 설명
  • 종수를 나타내는 정수
  • 샘플 입력 7 3 샘플 출력 4
    출처 2016 중북대학교 신입생 경기
    힌트는 돌이 모두 같기 때문에 순서만 다르면 같은 분법이다. 예를 들어 7을 3더미로 나누는 것(1,1,5)과(1,5,1)은 같은 것이다.
    주의는 딱 m더미, 한 무더기에 적어도 돌멩이 하나
    위에서 언급한 공식은 m를 초과하지 않으면 공더미가 m보다 적은 수에 적용되기 때문에 마지막 답은 (코드 보기)
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int maxn=1000000;
    int dp[50][50];
    int main(){
    	int n,m;
    	cin>>n>>m;
    	dp[0][0]=1;
    	for(int i=1;i<=m;i++){
    		for(int j=0;j<=n;j++){
    			if(j>=i){
    				dp[i][j]=dp[i][j-i]+dp[i-1][j];
    			}else
    			dp[i][j]=dp[i-1][j];
    		}
    	}
    	int ans=dp[m][n]-dp[m-1][n];//  
    	cout<

    우객 사과 같은 문제.https://www.nowcoder.com/questionTerminal/bfd8234bb5e84be0b493656e390bdebf
    M더미를 넘지 않는 경우;
    #include
    #include
    #include
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int maxn=1000000;
    int dp[50][50];
    int main(){
    	int n,m;
    	cin>>m>>n;
    	dp[0][0]=1;
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<=m;j++){
    			if(j>=i)
    			  dp[i][j]=dp[i][j-i]+dp[i-1][j];
    			else
    			  dp[i][j]=dp[i-1][j];  
    		}
    	}
    	int ans=dp[n][m];
    	cout<

    귀속
    소손님 이 문제 아래 토론에 상세한 해석이 있으니, 흥미가 있으면 한번 배워 보시오
     

    좋은 웹페이지 즐겨찾기