数位dp求分支
dp分析思路
状态计算之下一位填0的情况,下一位填1分析和它类似
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
char str[N];
int m; //易变数的最少操作次数
int g[N], f[N][N]; //g[]来表示要操作多少次才能变成1
int main()
{
scanf("%s%d", str, &m);
int n = strlen(str);//求出二进制位数
if(m == 0) puts("1"); //特判1
else if(m == 1) printf("%d\n", n - 1);//特判10,100,1000...
else
{
//因为n最多为1000位,全是1的话操作一次变为1000,本题1000即是最大的值了
for(int i = 2; i <= 1000; i ++) //打表预处理1000以内的情况
{
int cnt = 0; //求出二进制表示共有几个1
for(int j = i; j >= 1; j >>= 1)
{
if(j & 1) cnt ++;
}
g[i] = g[cnt] + 1;
}
for(int i = 1; i <= n; i ++) f[0][i] = g[i] == m - 1; //判断是否可以在m次内完成
for(int i = 1; i <= n; i ++)
{
for(int j = 0 ; j <= n; j ++)
{
f[i][j] += f[i - 1][j];
if(j + 1 <= n) f[i][j] = (f[i][j] + f[i - 1][j + 1]) % mod;
}
}
int res = 0, t = 0; //t用于下面求出当前位置i前面有几个1
for(int i = 0; i < n; i ++) //数位dp,开始求分支,求答案
{
if(str[i] == '1')
{
res = (res + f[n - i - 1][t]) % mod;
//当前位置:i,从i + 1 ~ n - 1位一共有 n - i - 1个数,前面t个1
t ++;
}
}
if(g[t] == m - 1) //特判右边边界上的最后一个数,它操作之后会变成t
res = (res + 1) % mod;
printf("%d\n", res);
}
return 0;
}
不懂就问,为什么for(int i = 1; i <= n; i ++) f[0][i] = g[i] == m - 1, 初始化时f[0][i]只能等于0或者1
这里要判断的是可不可以用m-1次操作将i变成1,所以f[0][i]只能等于0或者1。
因为字符串表示的二进制数操作一次后会变为1~1000内的数,即之前已经操作过一次了,所以这里我们判断时
只需要判断f[0][i] = g[i] == m - 1,
好的,谢谢大佬