簡單DP，N×M的網(wǎng)格其中有一條邊壞掉了，問從起點(diǎn)到終點(diǎn)的放法數(shù)

有兩種方法，一種是DP很好理解

?

1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 5 int dp[42][42]; 6 bool flag[42][42]; 7 8 int main(void) 9 { 10 #ifdef LOCAL 11 freopen("2125in.txt", "r", stdin); 12 #endif 13 14 int r, c; 15 while(scanf("%d%d", &r, &c) == 2) 16 { 17 int y1, x1, y2, x2; 18 scanf("%d%d%d%d", &y1, &x1, &y2, &x2); 19 dp[0][1] = 1; 20 memset(flag, false, sizeof(flag)); 21 flag[x1+1][y1+1] = flag[x2+1][y2+1] = true; 22 for(int i = 1; i <= r; ++i) 23 for(int j = 1; j <= c; ++j) 24 { 25 dp[i][j] = dp[i-1][j] + dp[i][j-1]; 26 if(flag[i][j]) 27 { 28 if(flag[i][j-1]) 29 dp[i][j] -= dp[i][j-1]; 30 if(flag[i-1][j]) 31 dp[i][j] -= dp[i-1][j]; 32 } 33 } 34 printf("%d\n", dp[r][c]); 35 } 36 return 0; 37 } 代碼君

?

第二種，用數(shù)學(xué)公式

如果沒有壞邊的話，總放法數(shù)是C^N-1_(M+N-2)?

因?yàn)槊糠N方法都要走(M+N-2)步，向上走N-1步，向下走M(jìn)-1步

現(xiàn)在考慮一條壞邊，那么就計算經(jīng)過這條壞邊的方案數(shù)然后從總數(shù)里面減去即可

經(jīng)過壞邊的放法數(shù)就是從起點(diǎn)到(x1, y1)的放法數(shù)×從(x2, y2)到終點(diǎn)的放法數(shù)

1 #define LOCAL 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 long long c(long long m, long long n) 8 { 9 if(m==0 || n==0) 10 return 1; 11 n = min(n, m-n); 12 long long ans = 1; 13 for(int i = 0; i < n; ++i) 14 ans = ans * (m-i) / (1+i); 15 return ans; 16 } 17 18 int main(void) 19 { 20 #ifdef LOCAL 21 freopen("2125in.txt", "r", stdin); 22 #endif 23 24 int n, m; 25 while(scanf("%d%d", &n, &m) == 2) 26 { 27 int x1, y1, x2, y2; 28 scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 29 if(x1+y1 > x2+y2) 30 { 31 int t = x1; 32 x1 = x2, x2 = t; 33 t = y1; 34 y1 = y2, y2 = t; 35 } 36 printf("%lld\n", c(m+n-2, m-1) - c(x1+y1, x1) * c(m+n-2-x2-y2, m-1-x2)); 37 } 38 return 0; 39 } 代碼君

?

轉(zhuǎn)載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/3931672.html

總結(jié)

以上是生活随笔為你收集整理的HDU 2125 Local area network的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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