hdu4734——数位dp(减去的艺术)

题目链接:https://vjudge.net/problem/HDU-4734

题目大意:求区间[l,r]内满足数x的F(x)<=F(a)的数的个数。

对于一个n位的数(AnAn-1An-2….A1),F(x)=An*2^(n-1)+An-1*2^(n-2)+…+A1*1.

题解:

首先我们肯定要维护一个状态sum表示枚举到pos位数的前面的数位的F(x)值,最后判断一下是否大于F(a)就行了。

因为F(x)最大为4599.所以这样是存的下的。

但是我们还需要再开一维存预先求出来的F(a),用来记录每一操作时对应的F(a)。

如果不用的话直接每次操作时都memset会超时。

但是这样一来空间又不够了,因此我们需要考虑一种状态既不需要存F(a),memset又可以在外面执行。

这里就体现了减去的艺术了。

定义新的状态为dp[pos][sum]表示枚举到当前pos位,后面还需要凑sum的权值和的个数。

至于为什么这样是可行的呢。

我们可以这样考虑,虽然F(a)是变的,但是每次大的F(a)总会用到小的F(a)。

而小的F(a)不会因为大的F(a)的改变而改变,因此大的sum会用到小的sum,但是小的sum不会因为F(a)的改变而改变。

代码实现:


#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#include
#include

#include
#include
#include
#define PI atan(1.0) * 4
#define E 2.718281828
#define rp(i, s, t) for (register int i = (s); i = (s); i--)
#define ll __int64
#define ull unsigned long long
#define mst(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define pii pair
#define mp make_pair
#define pb push_back
#define debug printf("ac\n");
using namespace std;
inline int read()
{
int a = 0, b = 1;
char c = getchar();
while (c '9')
{
if (c == '-')
b = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
a = (a << 3) + (a << 1) + c - '0';
c = getchar();
}
return a * b;
}
int a[20];
ll dp[20][5005];
ll MAX;
int num;
ll dfs(int pos,int sum,int lead,int limit){
if(pos==-1) return sumMAX) return 0;
if(!lead&&!limit&&dp[pos][MAX-sum]!=-1) return dp[pos][MAX-sum];
int up=limit?a[pos]:9;
ll ans=0;
rp(i,0,up){
ans+=dfs(pos-1,sum+i*(1<<pos),lead&&i==0,limit&&i==a[pos]);
}
if(!limit&&!lead) return dp[pos][MAX-sum]=ans;
return ans;
}
ll solve(ll x){
num=0;
while(x) a[num++]=x%10,x/=10;
return dfs(num-1,0,1,1);
}
int main(){
int T=read();
mst(dp,-1);
int kcase=0;
while(T--){
ll a,b;
scanf("%lld%lld",&a,&b);
MAX=0;
ll temp=1;
while(a){
MAX+=a%10*temp;
temp*=2;
a/=10;
}
// printf("%lld\n",MAX);
printf("Case #%d: %lld\n",++kcase,solve(b)-solve(0)+1);
}
return 0;
}

作者:木每立兄豪

相关推荐

在这里插入图片描述

【arduino中map函数】学习arduino这个函数你必须掌握…

在这里插入图片描述

python中关于报错信息“ModuleNotFoundError: No module named ‘numpy’”的处理方法

在这里插入图片描述

[LeetCode 周赛183] 4. 石子游戏 III(博弈dp、记忆化、巧妙解法)

《自拍教程53》Python_adb运行tcpdump工具

《自拍教程53》Python_adb运行tcpdump工具