CF-1013-F. Igor and Mountain（计数类dp）

思路讲解

感觉是dp，因为是计算路径数量。

首先我们将dp状态定义为到达该点的路径数量（其实也就是同一行之间只能从右往左转移）

然后转移方式如上图所示。

具体转移逻辑（代码）

	// dp指的是到达该点有多少种路径
	for(int i=N;i>=1;--i){
		sum[0]=0;
		// sum下面一行dp形成的前缀和
		for(int j=1;j<=M;++j){
			sum[j]=sum[j-1]+dp[i+1][j];
		}
		sumCur[0]=0;
		// sumCur为这一行形成的前缀和
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				dp[i][j]=dp[i][j]+sum[min(reachDis+j,M)]-sum[max(0ll,j-reachDis-1)];
				dp[i][j]%=mod;
				sumCur[j]=sumCur[j-1]+dp[i][j];
				sumCur[j]%=mod;
			}else{
				sumCur[j]=sumCur[j-1];
			}
		}
// #ifdef LOCAL
	// cerr<<"sumCur:";
    // for(int j=1;j<=M;++j){
    	// cerr<<sumCur[j]<<" ";
    // }
    // cerr<<"\n";
// #endif
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				// 相当于对这段区间进行了区间查询，但因为不能包括自己，所以还要减掉自己
				dp[i][j]=dp[i][j]+sumCur[min(D+j,M)]-sumCur[max(0ll,j-D-1)]-dp[i][j];
				dp[i][j]%=mod;
			}
		}
	}

AC代码

源代码

// Problem: F. Igor and Mountain
// Contest: Codeforces - Codeforces Round 1013 (Div. 3)
// URL: https://codeforces.com/contest/2091/problem/F
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=998244353;

ll N,M,D,T;
char maze[MAXN][MAXN];
// dpr指的是从右边到达该点有多少种状态 
// ll dpr[MAXN][MAXN],dpl[MAXN][MAXN];
ll dp[MAXN][MAXN];
ll sum[MAXN],sumCur[MAXN];

inline void solve(){
	cin>>N>>M>>D;
	// init
	for(int i=0;i<=N+5;++i){
		for(int j=0;j<=M+5;++j){
			dp[i][j]=0;
		}
	}
	bool haveAns=true;
	for(int i=1;i<=N;++i){
		bool haveHold=false;
		for(int j=1;j<=M;++j){
			cin>>maze[i][j];
			if(maze[i][j]=='X') haveHold=true;
		}
		if(!haveHold) haveAns=false;
	}
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif
	if(!haveAns){
		cout<<0<<"\n";
		return;
	}
	for(int i=1;i<=M;++i){
		if(maze[N][i]=='X') dp[N][i]=1;
	}
	// 1^2+?^2=d^2
	ll reachDis=sqrtl(D*D-1);	// 使用sqrtl保证精度
// #ifdef LOCAL
    // cerr << reachDis << '\n';
// #endif
	// dp指的是到达该点有多少种路径
	for(int i=N;i>=1;--i){
		sum[0]=0;
		// sum下面一行dp形成的前缀和
		for(int j=1;j<=M;++j){
			sum[j]=sum[j-1]+dp[i+1][j];
		}
		sumCur[0]=0;
		// sumCur为这一行形成的前缀和
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				dp[i][j]=dp[i][j]+sum[min(reachDis+j,M)]-sum[max(0ll,j-reachDis-1)];
				dp[i][j]%=mod;
				sumCur[j]=sumCur[j-1]+dp[i][j];
				sumCur[j]%=mod;
			}else{
				sumCur[j]=sumCur[j-1];
			}
		}
// #ifdef LOCAL
	// cerr<<"sumCur:";
    // for(int j=1;j<=M;++j){
    	// cerr<<sumCur[j]<<" ";
    // }
    // cerr<<"\n";
// #endif
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				// 相当于对这段区间进行了区间查询，但因为不能包括自己，所以还要减掉自己
				dp[i][j]=dp[i][j]+sumCur[min(D+j,M)]-sumCur[max(0ll,j-D-1)]-dp[i][j];
				dp[i][j]%=mod;
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=M;++i){
		ans+=dp[1][i];
	}
	ans%=mod;
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
// #ifdef LOCAL
   	// for(int i=1;i<=N;++i){
   		// for(int j=1;j<=M;++j){
   			// cerr<<dp[i][j]<<" ";
   		// }
   		// cerr<<"\n";
   	// }
   	// cerr<<"\n";
// #endif
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2091/submission/316079969
*/

心路历程（WA，TLE，MLE……）

这个测试组数7有点问题

https://codeforces.com/contest/2091/submission/316079483

最后发现是没取模，6.