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