$\quad $ 看到CTH立马就开始做了好吧,很适合当做入门题。
$\quad $ 首先定义 \(f[i]\) 表示进行到第 \(i\) 位时的答案数,\(bit\) 数组表示 \(01\) 序列。那么当 \(bit[i]\) 为 \(1\) 时,有
\[f[i]=\Sigma_{j=i+1}^{n+1} f[j]
\]
$\quad $ 至于为什么循环到 \(n+1\) ,循环到第 \(j\) 位时,我们要把这一位与后面的若干位(也许没有)划分到一起,当前位置的数可以和后面所有的数划分到一起,那么临界就是搜索第 \(n+1\) 位而非第 \(n\) 位。
$\quad $ 当 \(bit[i]\) 为 \(0\) 时,有
\[f[i]=f[i+1]
\]
$\quad $ 所以直接状态转移即可,或者 \(dfs\) 也行(不过都是 \(O(n^2)\) 的新的数据范围可以卡)。
DFS
#define yhl 0
#include"bits/stdc++.h"
using namespace std;
const int N=3e3+10,p=998244353;
int f[N],n,bit[N];
char ch[N];
int dfs(int pos){if(f[pos]!=-1)return f[pos];if(pos>=n)return 1;int ans=0;if(ch[pos]=='1')for(int j=pos+1;j<=n+1;j++)ans=(ans+dfs(j))%p;else ans=dfs(pos+1);return f[pos]=ans;
}
int main(){memset(f,-1,sizeof f);scanf("%d",&n);int nl=n;scanf("%s",ch+1);printf("%d",dfs(1));return yhl;
}
动归
#define yhl 0
#include"bits/stdc++.h"
using namespace std;
const int N=3e3+10,p=998244353;
int f[N],n;
char ch[N];
int main(){scanf("%d",&n);scanf("%s",ch+1);f[n+1]=1;for(int i=n;i>=1;i--){if(ch[i]=='1')for(int j=i+1;j<=n+1;j++)f[i]=(f[i]+f[j])%p;else f[i]=f[i+1];}printf("%d",f[1]);return yhl;
}
$\quad $ 其实看了动归代码我们可以发现转移时实际上是在求前缀和,直接拿数组维护一下即可,实际上我们并不需要定义一个数组,直接拿一个变量存即可,请读者自行理解。
$\quad $ 那么 \(dp\) 数组是不是也可以省掉呢?可以!
$\quad $ 所以最后 \(O(n)\) 的代码就出来了(doge)
点击查看代码
#define yhl 0
#include"bits/stdc++.h"
using namespace std;
const int N=3e3+10,p=998244353;
int ans=1,s=1,n;
char ch[N];
int main(){scanf("%d",&n);scanf("%s",ch+1);for(int i=n;i>=1;i--){if(ch[i]=='1')ans=s;s=(s+ans)%p;}printf("%d",ans);return yhl;
}