迷宫

1.朴素做法：记录在走到每个点能凑到哪些数，暴力转移,即 f [ i ] [ j ] [ k ] 表示能否有一条路径到 ( i , j ) 使路径和为k,空间稍大，但是如果定义为bool型变量能过
代码：

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&a[i][j]),a[i][j]%=M;
    f[1][0][0]=f[0][1][0]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=0;k<M;k++)
            {
                int las=((k-a[i][j])%M+M)%M;
                f[i][j][k]|=(f[i-1][j][las]|f[i][j-1][las]);
            }

    int ans=0;
    for (int i=0;i<M;i++) ans+=f[n][m][i];

    printf("%d\n",ans);

    return 0;

}

2.考虑优化——bitset优化

什么是bitset

bitset是c++中的一个类库，来管理一系列bit位，及二进制串。类似于数组，但每个元素只能是0或1且仅用1bit的空间

人话

对于这道题，我只能想到求出到每一个点能凑出的数。问题出在我该如何存储。这就是bitset的作用。他主要用于压位，因为所占空间较小。就比如说，如果需要计算一个二进制数中的1的个数，可以先将其转化为bitset

bitset<1001>a;
int main(){
    int x;cin>>x;a=x;
    cout<<a.count()<<"\n";
    return 0;
}

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+7,M=110;
const int mo=1e4+7;

bitset<N>b[M][M],x,y,z;
//十进制转二进制，取末尾mo位 
int n,m;
int a[M][M];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    //正常输入 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int xx=a[i][j]%mo;
            z=b[i-1][j]|b[i][j-1];
            x=z<<xx;
            y=z>>(mo-xx);
            b[i][j]=x|y;
            if(i==1&&j==1) b[1][1][xx]=1;
        }

    printf("%d\n",b[n][m].count());

    return 0;
}