【2019.7.16 NOIP模拟赛 T2】折叠（fold）（动态规划）

暴力\(DP\)

考虑暴力\(DP\)，我们设\(f_{i,j}\)表示当前覆盖长度为\(i\)，上一次折叠长度为\(j\)的方案数。

转移时需要再枚举这次的折叠长度\(k\)（\(k\ge j\)），转移方程如下：

\[f_{i+2k-j,k}+=f_{i,j}
\]

对于左、右两边，根据不同的初始化\(DP\)两遍。

统计时枚举两边覆盖长度计算即可。

优化\(DP\)

实际上，我们可以把这个\(DP\)拆成两个数组，一个表示左端点在\(x\)位的方案数，另一个表示右端点在\(y\)位的方案数。

转移时，方程也是比较简洁的：

\[a_{x+i}+=a_x,b_{x+2i}+=a_x
\]

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 10000

#define X 998244353

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

using namespace std;

int n,l,r;

class Dper

{

	private:

		int f[N+5],g[N+5],p[N+5];

	public:

		I void Solve()

		{

			#define DP(s,x,y) for(p[0]=i=1,t=n-y;i<=n;++i) p[i]=0;\

				for(i=x;2*i<=t;++i) for(j=0;2*i+j<=t;++j) Inc(p[i+j],p[j]),Inc(s[2*i+j],p[j]);++s[x];//用#define简洁表示两次DP

			RI i,j,t,ans=0;DP(f,l,r);DP(g,r,l);//DP预处理

			for(i=l;i<=n-r;++i) ans=(1LL*f[i]*g[n-i]+ans)%X,Inc(f[i+1],f[i]);printf("%d",ans);//统计答案

		}

}D;

int main()

{

	freopen("fold.in","r",stdin),freopen("fold.out","w",stdout);

	return scanf("%d%d%d",&n,&l,&r),D.Solve(),0;

}

巴特西

【2019.7.16 NOIP模拟赛 T2】折叠（fold）（动态规划）

暴力\(DP\)

优化\(DP\)

代码

最新文章

热门文章