首页 > 代码库 > HDU 2125 Local area network
HDU 2125 Local area network
简单DP，N×M的网格其中有一条边坏掉了，问从起点到终点的放法数
有两种方法，一种是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 LOCAL11 freopen("2125in.txt", "r", stdin);12 #endif13 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 }
第二种，用数学公式
如果没有坏边的话，总放法数是CN-1(M+N-2)
因为每种方法都要走(M+N-2)步，向上走N-1步，向下走M-1步
现在考虑一条坏边，那么就计算经过这条坏边的方案数然后从总数里面减去即可
经过坏边的放法数就是从起点到(x1, y1)的放法数×从(x2, y2)到终点的放法数
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 LOCAL21 freopen("2125in.txt", "r", stdin);22 #endif23 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 }
HDU 2125 Local area network
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。