题解：CF118D Caesar's Legions

· · 题解

Solution：

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

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

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

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

我们用 m[x][y][tot1][tot2] 表示在还剩 x 个步兵和 y 个骑兵且已有 tot1 或 tot2 个骑兵或步兵连续排列情况下的方案数。

奉上AC代码：

#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;
}