题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5632
------------------------------------------------------------------------------------------
这场比赛的官方题解说这题比较明显, 然而我比赛完后对着题解看了好久也没有想明白
于是先做了几道数位$DP$找找感觉 可惜感觉并没有找到
这题和传统数位$DP$不一样 这题是求范围内满足要求的数对的个数
既然是数对 我们记录时便不再记录数的状态 而是记录两数之间的关系的状态
不过官方题解只记录 考虑到了哪位 两数$1$的个数差的绝对值
大数$1$的个数是否不小于小数$1$的个数 这三个部分
可惜自己做的时候总感觉只记录这些状态还不够
然后$Cwind$前辈提供了一个思路 额外记录两个部分
大小两数当前位之前是否相等 大数当前位之前是否与限制条件相等
------------------------------------------------------------------------------------------
用以上的思路就可以比较轻松的用记忆化搜索做了
不过由于状态多两维 而且一开始的写法每次询问都需要重新计算 因而时间比较挫 要$1.4s$
观察后可发现如果较大数的当前位之前于限制条件不等 那么后面的数的选取都是任意的
所以这种情况下并不用每次重新计算 加了这个常数优化后要 $0.6s$
再加上一个对于当前状态贡献一定是$0$的剪枝后还要$0.48s$
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = , mod = ;
int f[N][N][][][], cnt[N][N][][][];//cnt记录的是时间戳
bool bin[N];
int num[];
char s[];
int t, len, n;
void init()
{
n = ;
while(len)
{
for(int i = len; i; --i)
{
num[i - ] += (num[i] & ) * ;
num[i] >>= ;
}
bin[++n] = (num[] != );
num[] = ;
if(!num[len])
--len;
}
}
int dfs(int x, int dif, bool over, bool same, bool top)
{
if(cnt[x][dif][over][same][top] == t + ||
(cnt[x][dif][over][same][top] && !top))
return f[x][dif][over][same][top];
cnt[x][dif][over][same][top] = t + ;
if(!x)
return f[x][dif][over][same][top] = !over;
if(over && dif >= x)
return f[x][dif][over][same][top] = ;
int re = ;
if(!top || bin[x])
{
re += dfs(x - , dif, over, same, top);
re += dfs(x - , dif + (over ? : -), over || dif == , , top);
re = (re >= mod ? re - mod : re);
}
if(!same)
{
re += dfs(x - , abs(dif + (over ? - : )), over && dif, , top && !bin[x]);
re = (re >= mod ? re - mod : re);
}
re += dfs(x - , dif, over, same, top && !bin[x]);
re = (re >= mod ? re - mod : re);
return f[x][dif][over][same][top] = re;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%s", s + );
len = strlen(s + );
for(int i = ; i <= len; ++i)
num[i] = s[len - i + ] - '';
init();
printf("%d\n", dfs(n, , , , ));
}
return ;
}
想到/理解了 更好的方法再来改改吧