题解：CF118D Caesar's Legions

Solution：

~~本蒟蒻的第一篇题解，大佬轻喷(；´д｀)ゞ~~

很显然，由数据得这种指数级别的暴搜会超时。

我们思考：上面的做法效率低下，是因为同一个状态会被访问多次。

如果我们每查询完一个状态后将该状态的信息存储下来，再次需要访问这个状态就可以直接使用之前计算得到的信息，从而避免重复计算。这充分利用了动态规划中很多问题具有大量重叠子问题的特点，属于用空间换时间的「记忆化」思想。

我们用 m[x][y][tot1][tot2] 表示在还剩

x

个步兵和

y

个骑兵且已有

tot1

或

tot2

个骑兵或步兵连续排列情况下的方案数。

奉上AC代码：

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e8;
int n1,n2,k1,k2,m[101][101][11][11];	//记忆化数组
int read()	//快读
{
	int x=0,a=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-') a=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=x*10+c-'0';
	return x*a;
}
int dfs(int x,int y,int tot1,int tot2)	//tot1，tot2分别表示已经选取了连续的几个步兵和骑兵，
										//x，y表示还有几个骑兵和步兵未选
{
	int ans=0;
	if(x==0&&y==0)	//方案成立，总数+1
	{
		ans=1;return ans;
	}
	if((x==0&&tot2>=k2)||(y==0&&tot1>=k1)) return 0;
	if(m[x][y][tot1][tot2]!=-1) return m[x][y][tot1][tot2];		//如果记录过直接返回
	if(x>0&&tot1<k1)
	{
		ans+=dfs(x-1,y,tot1+1,0);
		ans%=mod;
	}
	if(y>0&&tot2<k2)
	{
		ans+=dfs(x,y-1,0,tot2+1);
		ans%=mod;
	}
	m[x][y][tot1][tot2]=ans%mod;	//记录这种情况
	return ans%mod;
}
signed main()
{
//	freopen("a.in","r",stdin);
	n1=read();n2=read();
	k1=read();k2=read();
	memset(m,-1,sizeof m);	//建议赋一个比0小的初值，因为答案的情况可能为任意非负整数
	cout<<dfs(n1,n2,0,0)%mod;
	return 0;
}

题解：CF118D Caesar's Legions

文章操作

Solution：

奉上AC代码：

相关推荐

评论

题解：CF118D Caesar's Legions