【数位dp】[Scoi2014] bzoj3598 方伯伯的商场之旅

题目点这里

和方伯伯的斗争终于结束了。。。我也是快要死了。。。。（请自动忽视那两道非人哉的题 = =）

之前听学长说这题很水的数位dp ：）

对 水到我都做不起了。

 = =题解看了三遍啊！！！还是没研究明白这踏马是什么鬼！！

……总有种我数位dp白学了的感觉（其实确实也是白学了）

 思路……当然不是我想的…………

思路请见省选rank3大神：http://www.cnblogs.com/Artanis/p/3751644.html

代码……也是基本抄翔爷的…………

而且我是看着代码还想了两三个小时。。。。。。终于想通了

行了反正我就是渣 = = 这道题最终还是被我这么水过去了。。。。

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int read()
{
int sign = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }
while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }
return sign*n;
}

typedef long long LL;

LL L, R, K;
int bit[51];
LL dp[51][1505], num[51][2]; 
// Attention : 
// the meanings of dp[][] are changing

LL optimize(int pos, int change, int mid, bool limit)
{
if(!pos) return change;
if(!limit && (~dp[pos][change])) return dp[pos][change];

int sign = (pos >= mid) ? 1 : -1;
int d = limit ? bit[pos] : K - 1; LL ans = 0;
for(int i = 0; i <= d; ++i)
{
int next = change + sign * i; 
if(next < 0) break;
ans += optimize(pos - 1, next, mid, limit && (i == d));
}
if(!limit) dp[pos][change] = ans;
return ans;
}

LL dfs(int pos, bool limit)
{
if(!pos) return num[pos][limit] = 1, 0;
if(~dp[pos][limit]) return dp[pos][limit];

int d = limit ? bit[pos] : K - 1;
LL &f = dp[pos][limit] = 0, &n = num[pos][limit] = 0;
for(int i = 0; i <= d; ++i)
{
bool next = (limit && i == d);
f += dfs(pos - 1, next) + num[pos - 1][next] * i * (pos - 1);
n += num[pos - 1][next];
}
return f;
}

LL solve(LL n)
{
int len = 0;
for( ;n; n /= K) bit[++len] = n % K;
if(!len) return 0;
memset(dp, -1, sizeof(dp));
LL res = dfs(len, 1);
for(int i = 2; i <= len; ++i)
{
memset(dp, -1, sizeof(dp));
res -= optimize(len, 0, i, 1);
} 
return res;
}

int main()
{
ios::sync_with_stdio(false);
cin >> L >> R >> K;
cout << solve(R) - solve(L - 1) << endl;

return 0;
}