题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5632
------------------------------------------------------------------------------------------
这场比赛的官方题解说这题比较明显, 然而我比赛完后对着题解看了好久也没有想明白
于是先做了几道数位$DP$找找感觉 可惜感觉并没有找到
这题和传统数位$DP$不一样 这题是求范围内满足要求的数对的个数
既然是数对 我们记录时便不再记录数的状态 而是记录两数之间的关系的状态
不过官方题解只记录 考虑到了哪位 两数$1$的个数差的绝对值
大数$1$的个数是否不小于小数$1$的个数 这三个部分
可惜自己做的时候总感觉只记录这些状态还不够
然后$Cwind$前辈提供了一个思路 额外记录两个部分
大小两数当前位之前是否相等 大数当前位之前是否与限制条件相等
------------------------------------------------------------------------------------------
用以上的思路就可以比较轻松的用记忆化搜索做了
不过由于状态多两维 而且目前写法每次询问都需要重新计算 因而时间比较挫 要$1.4s$
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 const int N = 1000, mod = 998244353; 7 int f[N][N][2][2][2], cnt[N][N][2][2][2]; 8 bool bin[N]; 9 int num[310]; 10 char s[310]; 11 int t, len, n; 12 void init() 13 { 14 n = 0; 15 while(len) 16 { 17 for(int i = len; i; --i) 18 { 19 num[i - 1] += (num[i] & 1) * 10; 20 num[i] >>= 1; 21 } 22 bin[++n] = (num[0] != 0); 23 num[0] = 0; 24 if(!num[len]) 25 --len; 26 } 27 } 28 int dfs(int x, int dif, bool over, bool same, bool top) 29 { 30 if(cnt[x][dif][over][same][top] == t + 1) 31 return f[x][dif][over][same][top]; 32 cnt[x][dif][over][same][top] = t + 1; 33 if(!x) 34 return f[x][dif][over][same][top] = !over && !same; 35 int re = 0; 36 if(!top || bin[x]) 37 { 38 re += dfs(x - 1, dif, over, same, top); 39 re += dfs(x - 1, dif + (over ? 1 : -1), over || dif == 1, 0, top); 40 re = (re >= mod ? re - mod : re); 41 } 42 if(!same) 43 { 44 re += dfs(x - 1, abs(dif + (over ? -1 : 1)), over && dif, 0, top && !bin[x]); 45 re = (re >= mod ? re - mod : re); 46 } 47 re += dfs(x - 1, dif, over, same, top && !bin[x]); 48 re = (re >= mod ? re - mod : re); 49 return f[x][dif][over][same][top] = re; 50 } 51 int main() 52 { 53 scanf("%d", &t); 54 while(t--) 55 { 56 scanf("%s", s + 1); 57 len = strlen(s + 1); 58 for(int i = 1; i <= len; ++i) 59 num[i] = s[len - i + 1] - ‘0‘; 60 init(); 61 printf("%d\n", dfs(n, 0, 1, 1, 1)); 62 } 63 return 0; 64 }
想到/理解了 更好的方法再来改改吧
HDU 5632 Rikka with Array [想法题]
原文：http://www.cnblogs.com/sagitta/p/5225991.html