【算法】動態規劃+組合數學

【題意】有一個h行w列的棋盤，定義一些格子為不能走的黑點，現在要求從左上角走到右下角的方案數。

【題解】

大概能考慮到離散化黑點后，中間的空格子直接用組合數計算。

然后解決容斥問題就很重要了。

定義f[i]為走到第i個黑點且不經過其它黑點的方案數。

f[i]=calc(x[i]-1,y[i]-1)-Σ(f[j]*calc(x[i]-x[j],y[i]-y[j])),j<i&&x[j]<=x[i]&&y[j]<=y[i]。

calc(n,m)表示向右n步，向下m步的方案數，即C(n+m,n)。

這個轉移自帶容斥功能，從另一方面考慮，一條路徑到達黑點i，如果經過了若干黑點，那么只在它經過了第一個黑點的時候減去它。

那么f[i]減掉在其左上的所有f[j]（再乘j走到i的路徑數）就可以減去這樣的所有路徑了。

最后在右下角(h,w)增加一個黑點統計答案。

更多的想法參考：51nod1486 大大走格子?by?mrazer

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=2010,MOD=1e9+7; int f[maxn],fac[200010],h,w,n; struct cyc{int x,y;}a[maxn];bool cmp(cyc a,cyc b){return a.x<b.x||(a.x==b.x&&a.y<b.y);} void gcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;}else{gcd(b,a%b,y,x);y-=x*(a/b);} } int inv(int a){int x,y;gcd(a,MOD,x,y);return ((x%MOD)+MOD)%MOD; } int calc(int n,int m){return 1ll*fac[n+m]*inv(fac[n])%MOD*inv(fac[m])%MOD;}//1ll* int main(){scanf("%d%d%d",&h,&w,&n);fac[0]=1;for(int i=1;i<=h+w;i++)fac[i]=1ll*fac[i-1]*i%MOD;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);a[++n]=(cyc){h,w};sort(a+1,a+n+1,cmp);f[0]=1;for(int i=1;i<=n;i++){f[i]=calc(a[i].x-1,a[i].y-1);for(int j=1;j<i;j++)if(a[j].x<=a[i].x&&a[j].y<=a[i].y)f[i]=(f[i]+MOD-1ll*f[j]*calc(a[i].x-a[j].x,a[i].y-a[j].y)%MOD)%MOD;}printf("%d",f[n]);return 0; } View Code

?

轉載于:https://www.cnblogs.com/onioncyc/p/7566599.html

總結

以上是生活随笔為你收集整理的【51NOD】1486 大大走格子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。