How many ways

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2568????Accepted Submission(s): 1509

Problem Description 這是一個簡單的生存游戲，你控制一個機(jī)器人從一個棋盤的起始點(diǎn)(1,1)走到棋盤的終點(diǎn)(n,m)。游戲的規(guī)則描述如下：
1.機(jī)器人一開始在棋盤的起始點(diǎn)并有起始點(diǎn)所標(biāo)有的能量。
2.機(jī)器人只能向右或者向下走，并且每走一步消耗一單位能量。
3.機(jī)器人不能在原地停留。
4.當(dāng)機(jī)器人選擇了一條可行路徑后，當(dāng)他走到這條路徑的終點(diǎn)時，他將只有終點(diǎn)所標(biāo)記的能量。

如上圖，機(jī)器人一開始在(1,1)點(diǎn)，并擁有4單位能量，藍(lán)色方塊表示他所能到達(dá)的點(diǎn)，如果他在這次路徑選擇中選擇的終點(diǎn)是(2,4)

點(diǎn)，當(dāng)他到達(dá)(2,4)點(diǎn)時將擁有1單位的能量，并開始下一次路徑選擇，直到到達(dá)(6,6)點(diǎn)。
我們的問題是機(jī)器人有多少種方式從起點(diǎn)走到終點(diǎn)。這可能是一個很大的數(shù)，輸出的結(jié)果對10000取模。

?

Input 第一行輸入一個整數(shù)T,表示數(shù)據(jù)的組數(shù)。
對于每一組數(shù)據(jù)第一行輸入兩個整數(shù)n,m(1 <= n,m <= 100)。表示棋盤的大小。接下來輸入n行,每行m個整數(shù)e(0 <= e < 20)。 Output 對于每一組數(shù)據(jù)輸出方式總數(shù)對10000取模的結(jié)果. Sample Input 1 6 6 4 5 6 6 4 3 2 2 3 1 7 2 1 1 4 6 2 7 5 8 4 3 9 5 7 6 6 2 1 5 3 1 1 3 7 2 Sample Output 3948 講解這樣的題目 還是比較有意思的，看著像是搜索題目，但是吧，用常規(guī)搜索吧，容易超時，于是乎，動態(tài)規(guī)劃解決，還是挺簡單的； 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 #include<map> 8 #include<queue> 9 using namespace std; 10 int a[110][110]; 11 long long dp[110][110]; 12 const int mod=10000; 13 int main() 14 { 15 int k,t,m,n,k1,k2; 16 cin>>t; 17 while(t--) 18 { 19 k1=0;k2=0; 20 memset(dp,0,sizeof(dp)); 21 dp[1][1]=1; 22 cin>>m>>n; 23 for(int i=1;i<=m;i++) 24 for(int j=1; j<=n; j++) 25 scanf("%d",&a[i][j]); 26 for(int i=1; i<=m; i++ ) 27 for(int j=1 ;j<=n; j++) 28 { 29 k1=min(i+a[i][j],m); //在找到的點(diǎn)的右，下，開始dp； 30 for(int k=i ; k<=k1; k++) 31 { 32 k2=min(j+a[i][j]-k+i,n); 33 for(int l=j; l<=k2; l++) 34 { 35 if(k!=i || l!=j) 36 dp[k][l]=dp[k][l]+dp[i][j]; 37 if(dp[k][l]>=mod) dp[k][l]%=mod; 38 } 39 } 40 } 41 cout<<dp[m][n]%mod<<endl; 42 } 43 return 0; 44 }

?

總結(jié)

以上是生活随笔為你收集整理的HDU 1978 How many ways DP问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。