【组队赛#7】BNU 4275 Your Ways（数学题 + 动态规划）

【组队赛#7】BNU 4275 Your Ways（数学题 + 动态规划）

【题目链接】：​​click here~~​​

【题目大意】：题意：给出一个w*h的方格，问除去不能走的路，从(0,0)到(w,h)共有多少种走法。

【解题思路】：第七场比赛的题，最后一小时在看这道题，比较遗憾最后还是没有A出来，赛后重新看了看题目，理清一下思路，发现就是道简单的dp,

处理一下除去不能走的路，不过要注意题目的一句话：“ The blocking is done in such a way that it isnot possible to reach parts of the streets or avenues which is blocked from some other part which is blocked as well through any paths containingonly West-to-East and South-to-North walks.”，意思是说：阻塞的街道中分由西向东阻塞或者由南向北阻塞。一旦阻塞，意味着这条路不能通过，但是两边的点还是可以走的，阻塞的街道不影响其他可以走的街道。

因此，总的方案数如何求？用二维dp数组保存全部可以的方案， dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;（注意取模），那么总的方案数ans=dp[w][h],

不能走的方案数：res=dp[x1][y1]*dp[w-x2][h-y2](注意是乘！),最后答案就是（ans-res）%（mod）

代码：

#include using namespace std;#define mod 2552int t,w,h,k,x1,y1,x2,y2,ans,num;int dp[1010][1010];int main(){ cin>>t; while(t--) { cin>>w>>h>>k; int maxx=max(w,h); for(int i=0; i<=maxx; i++) dp[0][i]=dp[i][0]=1;//预处理 for(int i=1; i<=w; i++) for(int j=1; j<=h; j++){ dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;//总方案数 } // cout<>num; for(int i=1; i<=num; i++){ cin>>x1>>y1>>x2>>y2; ans-=dp[x1][y1]*dp[w-x2][h-y2];//总方案-阻塞的方案 ans=(ans+mod)%mod; } if(ans<0)ans+=mod; printf("%d\n",ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。