网站开发合同付款比例,外国人在中国做视频网站,wordpress只有vip会员下载,郑州粒米seo顾问传送门 文章目录题意#xff1a;思路题意#xff1a;
给你一个nmnmnm的方格#xff0c;你初始在(1,1)(1,1)(1,1)点#xff0c;有些位置有箱子#xff0c;你可以走到某个位置向你的方向推动这个箱子#xff0c;箱子不能出界#xff0c;问你走到(n,m)(n,m)(n,m)有多少种方…传送门 文章目录题意思路题意
给你一个n×mn×mn×m的方格你初始在(1,1)(1,1)(1,1)点有些位置有箱子你可以走到某个位置向你的方向推动这个箱子箱子不能出界问你走到(n,m)(n,m)(n,m)有多少种方案。
1≤n,m≤20001\le n,m\le 20001≤n,m≤2000
思路
没有箱子的时候就是一个裸的过河卒的问题了现在可以推动箱子而且是有方向的所以我们给原来的状态加一维代表上一次是从上还是左来的即f[i][j][op]f[i][j][op]f[i][j][op]表示从(i,j)(i,j)(i,j)到(n,m)(n,m)(n,m)op1op1op1代表从上面来op2op2op2代表从左面来这样路径的方案数考虑转移。
考虑某个位置(i,j)(i,j)(i,j)假设他上面没有箱子右边有xxx个箱子下面有yyy个箱子此时f[i][j][1]f[i][j][1]f[i][j][1]可以从∑ai,bj1ai,bm−xf[i][j][2]\sum_{ai,bj1}^{ai,bm-x}f[i][j][2]∑ai,bj1ai,bm−xf[i][j][2]注意这里需要用222来更新111不然会产生后效性。
可以发现向下也是这么转移的预处理一下x,yx,yx,y即可让后转移的话不能直接枚举所以搞一个后缀和即可。
复杂度O(nm)O(nm)O(nm)
// Problem: E. Rock Is Push
// Contest: Codeforces - Technocup 2020 - Elimination Round 2
// URL: https://codeforces.com/contest/1225/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N2010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
LL f[N][N][2],sum[N][N][2];
int l[N][N],r[N][N];
char s[N][N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;in;i) scanf(%s,s[i]1);if(n1m1) {cout(s[1][1]!R)endl;return 0;}for(int in;i1;i--) {for(int jm;j1;j--) {l[i][j]r[i][j]s[i][j]R;l[i][j]l[i][j1];r[i][j]r[i1][j];}}f[n][m][0]s[n][m]!R;f[n][m][1]s[n][m]!R;// sum[n][m][0]s[n][m]!R;// sum[n][m][1]s[n][m]!R;for(int in;i1;i--) {for(int jm;j1;j--) {// if(injm) continue;int xl[i][j1],yr[i1][j];f[i][j][0]sum[i1][j][1]-sum[n-y1][j][1];f[i][j][1]sum[i][j1][0]-sum[i][m-x1][0];f[i][j][0]%mod; f[i][j][1]%mod;f[i][j][0]mod; f[i][j][1]mod;f[i][j][0]%mod; f[i][j][1]%mod;sum[i][j][0]sum[i][j1][0]f[i][j][0];sum[i][j][1]sum[i1][j][1]f[i][j][1]; sum[i][j][0]%mod; sum[i][j][1]%mod;sum[i][j][0]mod; sum[i][j][1]mod;sum[i][j][0]%mod; sum[i][j][1]%mod;}}cout(f[1][1][0]f[1][1][1])%modendl;return 0;
}
/**/
