HDU 2151 Worm

3654 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=2151
Problem Description
クリスマスイブのりんごの値上げを見てから、Leleは彼の家の前にりんごの木を水平に植えて、全部でN本あった.
ふとLeleは左からP本目の木(1から数える)に毛虫がいるのを見つけた.毛虫が蝶になる過程を見るために、Leleはリンゴの木のそばで長い間観察していた.蝶は見えなかったが、Leleは1分ごとに毛虫がランダムに1本の木から隣の木に登るという法則を見つけた.
例えば、最初は2本目の木に毛虫がいましたが、1分後には1本目か3本目の木に毛虫がいる可能性があります.最初に毛虫が1本目の木にいたら、1分後には必ず2本目の木に毛虫がいます.
今あなたにリンゴの木の数Nを教えて、および毛のちょうど位置Pを始めて、お闻きして、M分の后で、毛虫はT本目の木に着いて、全部で何种类の歩く方案の数があります.

Input
この問題には複数のテストが含まれています.ファイルの終了(EOF)まで処理してください.
各グループのテストは1行を占め,4つの正の整数N,P,M,T(意味は問題記述,0
Output
データのセットごとに、1行に合計シナリオ数を出力します.
タイトルデータ保証答えが10^9未満

Sample Input

Sample Output


   
   
   
   
    
    
    
    4
0

    
    
    
     
      
      Hint 
                   ： 2->1->2->1->2 2->1->2->3->2 2->3->2->1->2 2->3->2->3->2

私にとても大きい1つのdpのテーマを助けて、もとはこのものを数えてdpを使うことができます!!!

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[120][105];
int main()
{
    int p,n,m,t;
    while(cin>>n>>p>>m>>t)
    {
        memset(a,0,sizeof(a));
        a[0][p]=1;
        for(int i=1;i<=m;i++)
        {
            a[i][1]=a[i-1][2];
            a[i][n]=a[i-1][n-1];
            for(int j=2;j<n;j++)
                a[i][j]=a[i-1][j-1]+a[i-1][j+1];
        }
        printf("%d
",a[m][t]);
    }
    return 0;
}

Problem Description
クリスマスイブのりんごの値上げを見てから、Leleは彼の家の前にりんごの木を水平に植えて、全部でN本あった.
ふとLeleは左からP本目の木(1から数える)に毛虫がいるのを見つけた.毛虫が蝶になる過程を見るために、Leleはリンゴの木のそばで長い間観察していた.蝶は見えなかったが、Leleは1分ごとに毛虫がランダムに1本の木から隣の木に登るという法則を見つけた.
例えば、最初は2本目の木に毛虫がいましたが、1分後には1本目か3本目の木に毛虫がいる可能性があります.最初に毛虫が1本目の木にいたら、1分後には必ず2本目の木に毛虫がいます.
今あなたにリンゴの木の数Nを教えて、および毛のちょうど位置Pを始めて、お闻きして、M分の后で、毛虫はT本目の木に着いて、全部で何种类の歩く方案の数があります.

Input
この問題には複数のテストが含まれています.ファイルの終了(EOF)まで処理してください.
各グループのテストは1行を占め,4つの正の整数N,P,M,T(意味は問題記述,0
Output
データのセットごとに、1行に合計シナリオ数を出力します.
タイトルデータ保証答えが10^9未満

Sample Input

Sample Output


    
    
    
    
     
     
     
     4
0

     
     
     
      
       
       Hint 
                    ： 2->1->2->1->2 2->1->2->3->2 2->3->2->1->2 2->3->2->3->2

义齿

[セットトップ]Springフレーム-JDBCのサポート