这周开始刷数位DP，在网上找到一份神级数位DP模板，做起题目来爽歪歪。
http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html
int dfs(int i, int s, bool e) {
if (i==-) return s==target_s;
if (!e && ~f[i][s]) return f[i][s];
int res = ;
int u = e?num[i]:;
for (int d = first?:; d <= u; ++d)
res += dfs(i-, new_s(s, d), e&&d==u);
return e?res:f[i][s]=res;
}
f为记忆化数组；
i为当前处理串的第i位（权重表示法，也即后面剩下i+1位待填数）；
s为之前数字的状态（如果要求后面的数满足什么状态，也可以再记一个目标状态t之类，for的时候枚举下t）；
e表示之前的数是否是上界的前缀（即后面的数能否任意填）。
for循环枚举数字时，要注意是否能枚举0，以及0对于状态的影响，有的题目前导0和中间的0是等价的，但有的不是，对于后者可以在dfs时再加一个状态变量z，表示前面是否全部是前导0，也可以看是否是首位，然后外面统计时候枚举一下位数。It depends.
于是关键就在怎么设计状态。当然做多了之后状态一眼就可以瞄出来。
HDU2098 不要62
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 15
int dp[maxn][],num[maxn];
int new_s(int s, int d)
{
if (d == ) return ;
else
{
return ;
}
}
int dfs(int i, int s, bool e) {
if (i == -) return ;
if (!e && ~dp[i][s]) return dp[i][s];
int res = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; ++d)
{
if (d==) continue;
if (s&&d==) continue;
res += dfs(i - , new_s(s, d), e && d == u);
}
return e ? res : dp[i][s] = res;
}
int cal(int n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , ,);
}
int main()
{
int l, r;
memset(dp, -, sizeof(dp));
while (scanf("%d%d", &l, &r) != EOF&&l+r)
{
printf("%d\n", cal(r) - cal(l -));
}
return ;
}
HDU3555 Bomb
和上题差不多
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 30
typedef long long LL;
LL dp[maxn][];
int num[maxn];
int new_s(int s, int d)
{
if (s == ) return ;
if (s == && d == ) return ;
if (d == ) return ;
return ; }
LL dfs(int i, int s, bool e)
{
if (i == -) return s == ;
if (!e&&~dp[i][s]) return dp[i][s];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
ret += dfs(i - , new_s(s, d), e&&d == u);
return e ? ret : dp[i][s] = ret; }
LL cal(LL n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , , );
}
int main()
{
int T;
scanf("%d", &T);
memset(dp, -, sizeof(dp));
while (T--)
{
LL n;
scanf("%I64d", &n);
printf("%I64d\n", cal(n));
}
return ;
}
BZOJ1026 windy数
注意前导0
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 30
typedef long long LL;
LL dp[maxn][];
int num[maxn];
LL dfs(int i, int s, bool e,int pre)
{
if (i == -) return s == ;
if (!e&&~dp[i][pre]&&s) return dp[i][pre];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
if(!s||abs(pre-d)>=)
{
ret += dfs(i - , s||d>, e&&d == u, d);
}
if (!e&&s)dp[i][pre] = ret;
return ret;
} LL cal(LL n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , , ,);
}
int main()
{
LL x,y;
memset(dp, -, sizeof(dp));
while (scanf("%lld%lld", &x,&y)!=EOF)
{
printf("%lld\n", cal(y)-cal(x-));
}
return ;
}
HDU3652 B-number
加一维，记录余数
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 30
typedef long long LL;
LL dp[maxn][][];
int num[maxn];
int new_s(int s, int d)
{
if (s == ) return ;
if (s == && d == ) return ;
if (d == ) return ;
return ;
}
LL dfs(int i, int s, bool e,int r)
{
if (i == -)
{
if ((s== ) && (r== )) return ;
else return ;
}
if (!e&&~dp[i][r][s]) return dp[i][r][s];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
{
ret += dfs(i - ,new_s(s,d) , e&&d == u, (r*+d)%);
}
return e ? ret : dp[i][r][s] = ret;
} LL cal(LL n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , , ,);
}
int main()
{
LL n;
memset(dp, -, sizeof(dp));
while (scanf("%I64d",&n)!=EOF)
{
printf("%I64d\n", cal(n));
}
return ;
}
HDU3943 K-th Nya Number
需要二分答案，还有就是注意区间范围是[P+1,Q]，被坑了好多发，还有我很不解的就是，memset放在最外面就会WA，每输入一组案例清空一次就AC了。。坑爹。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 25
typedef long long LL;
LL dp[maxn][maxn][maxn];
LL P, Q, x, y;
int num[maxn];
LL dfs(int i, int sx, int sy, bool e)
{
if (i == -)
{
if (sx == x&&sy == y) return ;
else return ;
}
if (!e&&~dp[i][sx][sy]) return dp[i][sx][sy];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
{
if (sx == x&&d == ) continue;
if (sy == y&&d == ) continue;
int a, b;
a = sx; b = sy;
if (d == ) a++;
if (d == ) b++;
ret += dfs(i - , a, b, e&&d == u);
}
return e ? ret : dp[i][sx][sy] = ret;
}
LL cal(LL n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , , , );
}
LL Bin(LL k)
{
LL l, r, mid, ans,ret;
ans = ;
ret = cal(P);
l = P+; r = Q;
while (l <= r)
{
mid = (l + r) >> ;
if (cal(mid) - ret>= k)
{
ans = mid;
r = mid - ;
}
else l = mid + ;
}
return ans;
}
int main()
{
int T,kase=;
scanf("%d", &T); while (T--)
{
int n;
memset(dp, -, sizeof(dp));
scanf("%I64d%I64d%I64d%I64d", &P, &Q, &x, &y);
scanf("%d", &n);
printf("Case #%d:\n", ++kase);
while (n--)
{
LL k;
scanf("%I64d",&k);
LL ans = Bin(k);
if (ans)
printf("%I64d\n", ans);
else printf("Nya!\n");
}
}
return ;
}
POJ3208 Apocalypse Someday
做法和上题一样，需要注意的是它是必须有连续的三个6，还有就是二分的上界尽量大。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 30
typedef long long LL;
LL dp[maxn][];
int num[maxn];
int new_d(int s, int d)
{
if (s == ) return ;
int st = s;
if (d == ) s++;
return st==s?:s;
}
LL dfs(int i, int s,bool e)
{
if (i == -) return s == ;
if (!e&&~dp[i][s]) return dp[i][s];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
{
ret += dfs(i - , new_d(s,d),e&&d == u);
}
return e ? ret : dp[i][s] = ret;
}
LL cal(LL n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , , );
}
LL Bin(LL k)
{
LL l, r, mid, ans,ret;
ans = ;
l = , r = 100000000000LL;
while (l <= r)
{
mid = (l + r) >> ;
if (cal(mid)>= k)
{
ans = mid;
r = mid - ;
}
else l = mid + ;
}
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
LL k;
memset(dp, -, sizeof(dp));
scanf("%I64d", &k);
printf("%I64d\n", Bin(k));
}
return ;
}
SPOJ BALNUM Balanced Numbers
刚开始一直不知道该怎么记录前面的状态，搜了下解题报告，用的是三进制来表示前面的状态(此题的精华就是这里吧。。)，因为状态总数为3^10，因此也不大。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 66666
typedef long long LL;
LL dp[][maxn];
int num[];
int cnt[];
void go(int s)
{
for (int i = ; i < ; i++)
{
cnt[i] = s % ;
s /= ;
}
}
int new_s(int s, int d)
{
go(s);
if (cnt[d] == ) cnt[d] = ;
else
cnt[d] = - cnt[d];
int base = ;
s = ;
for (int i = ; i < ; i++)
{
s += base * cnt[i];
base *= ;
}
return s;
}
int check(int s)
{
go(s);
for (int i = ; i < ; i++)
{
if ((i & ) && (cnt[i] == )) return ;
if (!(i & ) && (cnt[i] == ))return ;
}
return ;
}
LL dfs(int i, int s, bool e,int zero)
{
if (i == -) return check(s);
if (!e&&~dp[i][s]) return dp[i][s];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
{
ret += dfs(i - , zero&&d==?:new_s(s, d), e&&d == u,zero&&d==);
}
return e ? ret : dp[i][s] = ret;
}
LL cal(LL n)
{
int cnt = ;
while (n)
{
num[cnt++] = n % ;
n /= ;
}
return dfs(cnt - , , ,);
}
int main()
{
int T;
scanf("%d", &T);
memset(dp, -, sizeof(dp));
while (T--)
{
LL x, y;
scanf("%lld%lld", &x, &y);
printf("%lld\n", cal(y) - cal(x - ));
}
return ;
}
SPOJ MYQ10 Mirror Number
每个数字只可能是0,1,8，区间比较大0 <= a<=b <= 10^44，所以输入要用字符串，一般我们求答案都是：cal(b)-cal(a-1),但此题是字符串，因此需要特殊下a是不是Mirror Number,还被坑了好久的就是，由于是字符串输入，最高位的下标是0。。然后我没有反转过来。。找了好久才发现。。用一个数组记录前面选的数（之前的状态），只要第一个非0位确定就可以知道回文串的长度，也就知道回文串中心的位置，然后从中心更低的位置开始判断是不是回文。前导0也需要注意
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 50
typedef long long LL;
LL dp[maxn][maxn];
int num[maxn],tmp[maxn];
LL dfs(int i, int len, bool e,int zero)
{
if (i == -) return ;
if (!e&&~dp[i][len]) return dp[i][len];
LL ret = ;
int u = e ? num[i] : ;
for (int d = ; d <= u; d++)
{
if (d!=&&d!=&&d!=) continue;
if (zero)
{
tmp[i] = d;
ret += dfs(i - , len - !d, e&&d == u, zero&& d == );
}
else
{
int mid = len / ;
int fg = i < mid ? : ;
if (fg)
{
if (tmp[len - i - ] == d)
ret += dfs(i - , len, e&&d == u, zero);
}
else
{
tmp[i] = d;
ret += dfs(i - , len, e&&d == u, zero);
}
}
}
return e ? ret : dp[i][len] = ret;
}
LL cal(char *s)
{
int cnt = strlen(s);
for (int i = ; i < cnt; i++) num[cnt-i-] = s[i] - '';
return dfs(cnt - , cnt, ,);
}
int ok(char *s)
{
int len = strlen(s);
for (int i = ; i < len; i++)
if (s[i] != ''&& s[i] != ''&&s[i] != '') return ;
for (int i = ; i < len / ; i++)
if (s[i] != s[len - i - ]) return ;
return ;
}
int main()
{
int T;
scanf("%d", &T);
memset(dp, -, sizeof(dp));
while (T--)
{
char x[maxn], y[maxn];
scanf("%s%s", x, y);
printf("%lld\n", cal(y) - cal(x)+ok(x));
} return ;
}