正題

題目鏈接:https://jzoj.net/senior/#contest/show/3014/1

---

題目大意

$n?m$的格子，開始在$(n,1)$，每次可以右拐或者往前，不能走重復(fù)的和障礙，求有多少種方案到達(dá)$(y,x)$

---

解題思路

設(shè)$f_{s,x1,y1,x2,y2}$表示目前朝向?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$s$，先前所走的范圍都在$(x1,y1,x2,y1)$這個(gè)矩形內(nèi)的方案數(shù)。

要滾動(dòng)，我們枚舉$i$表示這個(gè)矩形 長+寬=$i$ 然后進(jìn)行$dp$即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define star(x,y) ((x)==sx&&(y)==sy) using namespace std; const ll N=101; const ll dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; ll n,m,sx,sy,p,f[2][4][N][N][N],ans; ll v1[N][N],v2[N][N]; char s[N]; int main() {scanf("%lld%lld%lld",&n,&m,&p);scanf("%lld%lld",&sy,&sx);for(ll i=1;i<=n;i++){scanf("%s",s+1);for(ll j=1;j<=m;j++){v1[i][j]=v1[i][j-1]+(s[j]=='*');v2[i][j]=v2[i-1][j]+(s[j]=='*');}}for(ll i=2;i<=n+m;i++){for(ll x=1;x<i;x++){ll y=i-x;for(ll h=1;h<=sx&&x+h-1<=n;h++)for(ll w=1;w<=sy&&y+w-1<=m;w++){ll zx=x+h-1,zy=y+w-1;if(zx<sx||zy<sy) continue;f[i&1][0][h][w][zx]=(f[~i&1][0][h][w][zx]+(v1[h][zy]-v1[h][w-1]==0)*(f[~i&1][1][h+1][w][zx]+star(h,zy)))%p;f[i&1][1][h][w][zx]=(f[~i&1][1][h][w][zx-1]+(v2[zx][zy]-v2[h-1][zy]==0)*(f[~i&1][2][h][w][zx]+star(zx,zy)))%p;f[i&1][2][h][w][zx]=(f[~i&1][2][h][w+1][zx]+(v1[zx][zy]-v1[zx][w-1]==0)*(f[~i&1][3][h][w][zx-1]+star(zx,w)))%p;f[i&1][3][h][w][zx]=(f[~i&1][3][h+1][w][zx]+(v2[zx][w]-v2[h-1][w]==0)*(f[~i&1][0][h][w+1][zx]+star(h,w)))%p;} }}printf("%lld",f[(n+m)&1][3][1][1][n]);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的jzoj4019-Path【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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