soj1763.패스 게임

4437 단어 플레이
제목은 어렵지 않고 dp의 전이 방정식도 쉽게 열거할 수 있다.
dp[i][j]를 설정하면 i번째 패스 후 공이 j의 손에 들어오는 패스 수를 대표한다.얻기 쉽다
dp[i][j]=dp[i-1][j-1]+dp[i-1][j-1]를 머리와 꼬리를 다시 처리하면 됩니다.
 1 #include <iostream>

 2 #include <memory.h>

 3 using namespace std;

 4 int dp[32][32];

 5 int main()

 6 {

 7     int n,m;

 8     while(cin >> n >> m)

 9     {

10         memset(dp,0,sizeof(dp));

11         int i,j;

12         dp[1][n] = 1;

13         dp[1][2] = 1;

14         for(i = 2;i <= m;i++)

15         {

16             for(j = 1;j <= n;j++)

17             {

18                 if(j == 1)

19                     dp[i][j] = dp[i-1][j+1] + dp[i-1][n];

20                 else if(j == n)

21                     dp[i][j] = dp[i-1][j - 1] + dp[i-1][1];

22                 else

23                     dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];

24             }

25         }

26         cout << dp[m][1] << endl;

27     }

28     return 0;

29 }

좋은 웹페이지 즐겨찾기