POJ 1664 사과 n개를 쟁반에 넣는 방법에 따라 분류 토론

1174 단어 user
분류 토론을 통해 규모가 비교적 큰 문제를 규모가 비교적 작은 같은 문제로 전환하고'차원 낮추기'를 배워서 색인 값을 끊임없이 낮추면 답안을 구할 수 있다
f(m, n)를 n개의 접시에 사과 m개를 넣는 방법으로 m>=0, n>=0.만약 m와 n 중 어느 것이 0과 같다면 f(m, n)=1, 주의는 0이 아니다. 왜냐하면 그 결과는 접시에 (사과가 없고) 넣지 않거나 접시도 없기 때문이다.
n=1이면 임의의 m>=0에 f(m, 1)=1 있음
만약 m=1이라면 임의의 n>=0에 f(1,n)=1
다음은 m>1 & n>1의 상황을 토론합니다.
m만약 m>=n이면 대체적으로 두 가지 방법이 있다.
첫 번째 상황: 적어도 한 접시가 비어 있으면 아무것도 넣지 않는다. 이 부분의 방법은 f(m, n-1)이다.두 번째 상황: 모든 접시에 사과가 있습니다. 그러면 먼저 m개의 사과에서 n개를 뽑아내고 각 접시를 하나씩 나누어 나머지 m-n개의 사과를 n개의 접시에 넣는 방법을 고려하여 f(m, n)를 f(m-n, n)로 낮추는 데 성공했습니다.
그래서 m>=n시 f(m, n)= f(m, n-1)+f(m-n, n);
Source Code
Problem: 1664
 
User: yangliuACMer
Memory: 384K
 
Time: 0MS
Language: GCC
 
Result: Accepted
#include<stdio.h>
int f(int x,int y){
	if(y ==1||x==0) return 1;
	if(x<y) return f(x,x);
	return f(x,y-1)+f(x-y,y);// 
}

void main(){
	int t,m,n,i;
	scanf("%d",&t);
	for(i=0;i<t;i++){
		scanf("%d%d",&m,&n);
		printf("%d
",f(m,n)); } }

좋은 웹페이지 즐겨찾기