HDU2151 【DP】

1880 단어
M은 분, T는 위치, A[M][T]로 가는 방법은 A[M-1][T-1]+A[M-1][T+1]'
DP의 정수는 상태 방정식을 찾는 것이다. 왜냐하면 두 방향만 목표 지점에 도달할 수 있기 때문이다.
Description
크리스마스이브에 사과 값이 오르는 것을 본 후, 릴은 그의 집 입구에 수평으로 한 줄의 사과나무를 심었는데, 모두 N그루가 있었다.
 
갑자기 Lele은 왼쪽부터 P그루의 나무(1부터 계수)에 모충 한 마리가 있는 것을 발견했다.레어는 애벌레가 나비로 변하는 과정을 보기 위해 사과나무 옆에서 오랫동안 관찰했다.나비는 보지 못했지만 릴리는 1분마다 모충이 랜덤으로 나무에서 이웃 나무로 기어오르는 규칙을 발견했다.
 
예를 들어 처음에 모충이 두 번째 나무에 있었는데 1분이 지나면 모충이 첫 번째 나무나 세 번째 나무에 있을 수도 있다.만약 처음에 모충이 첫 번째 나무에 있었다면, 1분이 지나면 모충은 반드시 두 번째 나무에 있었을 것이다.
 
지금 사과나무의 숫자 N과 털이 처음 있는 위치 P를 알려드릴게요. M분 후에 털벌레가 T그루 나무에 도착하면 모두 몇 가지 걷기 방안이 있나요?
 
 
Input
이 문제는 여러 개의 테스트를 포함하고 있습니다. 파일이 끝날 때까지 처리하십시오. (EOF)
 
각 그룹의 테스트는 네 개의 정수 N, P, M, T를 포함하여 한 줄을 차지한다. (의미는 제목 설명, 0 
 
Output
각 그룹의 데이터에 대해 한 줄에 전체 방안 수를 출력합니다.
 
문제 데이터는 답안이 10^9보다 적음을 보증합니다
 
 
Sample Input

     
     
     
     
3 2 4 2 3 2 3 2

 
Sample Output

      
      
      
      
4 0
#include <bits/stdc++.h>
using namespace std ;
int dp[150][150];
//*M   ,T   ,  A[M][T]    A[M-1][T-1]+A[M-1][T+1]*// 
int main()
{
	int n,p,m,t;
	int sum;
	while(cin>>n>>p>>m>>t)
	{
		memset(dp,0,sizeof(dp));
		int i , j ;
		dp[m][t]=1;
		for(i=m-1;i>=0;i--)
		{
			for(j=1;j<=n;j++)
			{
				if(j-1>0)
				{
					dp[i][j]+=dp[i+1][j-1]; 
				}
				if(j+1<=n)
				{
					dp[i][j]+=dp[i+1][j+1];
				}
			}
			
		}
		cout<<dp[0][p]<<endl;
	}
	return 0 ;
}

좋은 웹페이지 즐겨찾기