POJ 1664 (동규)
보 니 마 라 는 물 은 내 가 오랫동안 생각 했 는데...................................................................
사실 이 문 제 는 매우 간단 한 동태 계획 으로 제목 의 뜻 에 따라 이 문 제 는 두 가지 상태 로 나 눌 수 있다.
1. nPlate > nApple 이 있 을 때 (nPlate - nApple) 개의 접시 가 비어 있 을 것 입 니 다. 이 빈 접 시 를 없 애 도 마지막 결과 에 영향 을 주지 않 습 니 다. 상태 전이 방정식 은 F (nPlate, nApple) = F (nApple, nApple) 입 니 다.
2. nPlate < nApple 때 이런 상 태 는 두 가지 상태의 합 이다. 하 나 는 일부러 한 접 시 를 비 워 서 사 과 를 넣 지 않 는 것 이 고 다른 하 나 는 접시 마다 적어도 한 개의 사과 가 있 는 것 이다. 이때 사과 의 수량 은 (nApple - nPlate) 으로 변 할 수 있다.
상태 이동 방정식 은 F (nPlate, nApple) = F (nPlate - 1, nApple) + F (nPlate, nApple - nPlate)
재 귀 경계 에 대하 여 우 리 는 이 몇 가지 상황 을 고려 할 수 있다.첫 번 째 는 이때 사과 가 몇 개 더 있 든 접시 가 하나 밖 에 남지 않 았 으 니 방법 은 하 나 를 더 할 수 있다 는 것 이다.두 번 째 는 사과 가 없어 접시 가 있 든 없 든 끝 이 야. 하나 더.세 번 째 는 사과 가 하나 남 았 는데 접시 가 몇 개 남 았 든 방법 은 딱 하나 다.
아래 윗 파 C 초두 실현
#include
#include
#include
#include
// ， ，
int DFS(int nPlate, int nApple)
{
if(nPlate == 1 || nApple == 0 || nApple == 1)
return 1;
else if(nPlate > nApple)
return DFS(nApple, nApple);
else
return DFS(nPlate-1,nApple) + DFS(nPlate, nApple-nPlate);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int M, N;
scanf("%d %d",&M, &N);
printf("%d
",DFS(N, M));
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
