动态规划

DP训练——数位DP

2020-02-24  本文已影响0人  云中翻月

数位DP

BZOJ1026
题意
求A到B(A,B<=2000000000)间，不含前导零且相邻两个数字之差至少为2的正整数的个数。
题解
状态定义：f[x,st,op]表示当前处理到第x位，上一位为st，是否达到上限状态为op的方案数
目标：solve(B)-solve(A-1)
边界：f[0,,]=1
转移方程：f[x,st,op]=\sum_{i=1}^{maxx}f[x-1,i,i==maxx \&\& op]
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000000000+5;
const int maxl=10+2;
const int INF=0x3f3f3f3f;
int A,B;
vector<int>v;
int f[maxl][maxl][2];
int dfs(int x,int st,int op){
    if(!x) return 1;
    if(~f[x][st][op]) return f[x][st][op];
    int res=0;
    int maxx=op?v[x]:9;
    for(int i=0;i<=maxx;i++){
        if(abs(st-i)<2) continue;
        if(st==11&&i==0) res+=dfs(x-1,11,op&&(i==maxx)); //存在前导0 所以后面的选择方案数依然不受限制 
        else res+=dfs(x-1,i,op&&(i==maxx));
    }
    return f[x][st][op]=res;
}
int solve(int x){
    memset(f,-1,sizeof(f));
    v.clear();
    v.push_back(-1);
    while(x){
        v.push_back(x%10);
        x/=10;
    }
    return dfs(v.size()-1,11,1); //st=11 表示没有相邻位的限制
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("BZOJ1026.in","r",stdin);
    cin>>A>>B;
    cout<<solve(B)-solve(A-1);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endi

BZOJ3131
题意
给定n*n(n<=1e12)的方格，每个点(i,j)会为点(f(i),f(j))带来一个权值为1的贡献，其中f(i)表示i在十进制下各位数字之积。
求最大k(k<=1e5)个权值的和对1e9+7取模。
题解
预处理出所有范围在[1,n]内的积，离散化后存储在数组ls中。
接下来进行数位dp，求出数组\_hash[i]表示有多少个数字各个位相乘后的结果是ls[i]的。
于是便可以根据\_hash数组进行多路归并，求出前k个最大的权值了。
状态定义：f[x,st,op]表示当前处理到第x位，当前积为st，是否达到上限状态为op的方案数
目标：\_hash数组
边界：f[0,st!=0,]=1
转移方程：f[x,st,op]=\sum_{i=1}^{maxx}f[x-1,st/i,i==maxx \&\& op]
题解链接 https://blog.csdn.net/xiaoming_p/article/details/79560210
代码如下

/*

*/
#define method_2
#ifdef method_1

#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500000+5;
const int maxm=15000+5;
const int maxl=20+5;
const int INF=0x3f3f3f3f;
const ll mod=1000000007;
ll n;
int k;
int z[maxl],sz=0,cnt=0;
ll d[maxl][maxm][2],_hash[maxm],ls[maxn];
map<ll,int>mp;
void dfs(ll now){  //预处理出所有的积，积的范围在[1,n]以内
    if(now>n) return;
    if(mp[now]) return;
    mp[now]=1;
    ls[++cnt]=now;
    for(int i=1;i<=9;i++) dfs(now*i);
}
void pre(ll x){ 
    while(x){
        z[++sz]=x%10;
        x/=10;
    }
    dfs(1);
    sort(ls+1,ls+cnt+1);
    cnt=unique(ls+1,ls+cnt+1)-ls-1;
}
ll dp(int pos,int j,int lim){ //当前处理到第pos位，处理的乘积是离散数组（ls）的第j个数，是否达到上限状态为lim
    if(pos<1) return j==1;
    if(~d[pos][j][lim]) return d[pos][j][lim];
    ll ret=0;
    int up=lim?z[pos]:9;
    for(int i=1;i<=up;i++){
        if(ls[j]%i) continue; //不能整除
        ret+=dp(pos-1,lower_bound(ls+1,ls+cnt+1,ls[j]/i)-ls,lim&&(i==z[pos]));
    }
    return d[pos][j][lim]=ret;
}
struct data{
    int id1,id2;
    ll d;
    friend bool operator<(data a,data b){
        return a.d<b.d;
    }
};
priority_queue<data>q;
void solve(){
    ll ans=0;
    memset(d,-1,sizeof(d));
    //_hash[i]表示有多少个数字各个位相乘后的结果是ls[i]的
    for(int i=1;i<=cnt;i++) _hash[i]+=dp(sz,i,1); //处理位数相同的
    for(int i=1;i<sz;i++) for(int j=1;j<=cnt;j++) _hash[j]+=dp(i,j,0); //处理位数较小的
    sort(_hash+1,_hash+cnt+1);
    reverse(_hash+1,_hash+cnt+1);
    for(int i=1;i<=cnt;i++) if(_hash[i]==0){
        cnt=i-1;
        break;
    }
    
    for(int i=1;i<=cnt;i++) D(_hash[i]);
    E;
    
    //_hash表里面任意选(i,j),_hash[i]*_hash[j]即表示为某个格子带来权值的原始格子数（即一个格点的最终权值）
    for(int i=1;i<=cnt;i++) q.push((data){i,1,_hash[1]*_hash[i]}); 
    for(int i=1;i<=k;i++){
        if(q.empty()) break;
        data temp=q.top();q.pop();
//        D(temp.id1);D(temp.id2);D(temp.d);E;
        ans=(ans+temp.d)%mod;
        if(temp.id2<cnt) q.push((data){temp.id1,temp.id2+1,_hash[temp.id1]*_hash[temp.id2+1]});
    }
    cout<<ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ3131.in","r",stdin);
    cin>>n>>k;
    pre(n);
    solve();
    return 0;
}
#endif

BZOJ4521
题意
求A到B(1e10<=A,B<=1e11)间，不含前导零。至少存在3个相邻的相同数字，且不能同时出现8和4的正整数的个数。
题解
状态定义：f[x,st1,st2,st,op1,op2,op3]表示处理到第x位，i-2位为st1，i-1位为st2，是否出现了连续三个数字的状态为st，4是否出现状态为op1，8是否出现状态为op2，是否与上限相等为op3的答案
目标：solve(B)-solve(A-1)
边界：f[0,...]=1
转移方程：f[x,st1,st2,st,op1,op2,op3]=\sum_{i=1}^{maxx}f[x-1,st2,i,(i==st2\&\&i==st1),op1||(i==4),op2||(i==8),i==maxx \&\& op3]
PS：
通过如下方式可避开第一位上的前导0：枚举1到第一位上的数字，从下一位开始搜索。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const ll maxn=1e11+5;
const int maxl=11+2;
const int INF=0x3f3f3f3f;
ll A,B;
vector<int>v;
ll f[maxl][maxl][maxl][2][2][2][2];
//f[i,st1,st2,st,op1,op2,op3]表示处理到第i位，i-2位为st1，i-1位为st2，是否出现了连续三个数字的状态为st，4是否出现状态为op1，8是否出现状态为op2，是否与上限相等为op3的答案
ll dfs(int x,int st1,int st2,int st,int op1,int op2,int op3){
    if(op1&&op2) return 0ll;
    if(!x) return (ll)st;
    if(~f[x][st1][st2][st][op1][op2][op3]) return f[x][st1][st2][st][op1][op2][op3];
    ll res=0;
    int maxx=op3?v[x]:9;
    for(int i=0;i<=maxx;i++){
//        if(op1==1&&i==8) continue;
//        if(op2==1&&i==4) continue;
        res+=dfs(x-1,st2,i,st||(i==st2&&i==st1),op1||(i==4),op2||(i==8),op3&&(i==maxx));
    }
    return f[x][st1][st2][st][op1][op2][op3]=res;
}
ll solve(ll x){
    if(x<1e10) return 0;
    memset(f,-1,sizeof(f));
    v.clear();
    v.push_back(-1);
    while(x){
        v.push_back(x%10);
        x/=10;
    }
    ll ans=0ll;
    //问:如何避开第一位上的前导0
    //答:枚举1到第一位上的数字，从下一位开始搜索
    for(int i=1;i<=v[v.size()-1];i++){
        ans+=dfs(v.size()-2,-1,i,0,i==4,i==8,i==v[v.size()-1]);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ4521.in","r",stdin);
    cin>>A>>B;
    cout<<solve(B)-solve(A-1);

    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ3598
题意
给出A，B(A,B<=1e15)，k，求将A与B之间的数进行x操作的最小代价。
x操作指将一个数转化为k进制，表示有几堆石块，每堆石块恰有该数位上的数个石子，相邻两堆距离为1。
现要将一个数对应的若干石块堆合并为一堆，单次代价为移动石块数*两堆石块间的距离。
题解
首先考虑计算一个数的合并代价，则需要确定最终合并的位置。
实现上，可以先计算出将所有石块都合并到最右边（即数字最低位）的代价。
然后不断尝试将最终合并点左移，通过判断前缀和的正负来确定移动调整后是否会使得结果更优。
（之所以考虑计算前缀和正负，是因为每向左移动一次，对答案的贡献是右边的数字和-左边的数字和）
而要计算[A,B]间所有数字的情况，只需要在上述过程中加入一个数位dp即可。
状态定义：
f[x,st,op]表示处理到第x位，代价和为st，是否与上限相等为op的答案
d[x,st,op]表示处理到第x位，前缀和为st，是否与上限相等为op的答案
目标：solve(B)-solve(A-1)
边界：
f[0,,]=st
d[0,,]=st
转移方程：
f[x,st,op]=\sum_{i=1}^{maxx}f[x-1,st+i*(x-1),i==maxx \&\& op]
d[x,st,op]=\sum_{i=1}^{maxx}f[x-1,st+/-i(+-符号取决于i与枚举的合并点mid之间的大小关系),i==maxx \&\& op]
题解链接 https://blog.csdn.net/yzyyylx/article/details/79488044
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const ll maxn=1e15+5;
const int maxl=15*5+5; //log2(1e15)
const int maxs=250+5; //前缀和最大值
const int maxp=2000+5; //代价和最大值
const int INF=0x3f3f3f3f;
ll A,B;
int K;
vector<int>v;
ll f[maxl][maxp][2];
ll d[maxl][maxs][2];
//f[i,st,op]表示处理到第i位，代价和为st，是否与上限相等为op的答案
//d[i,st,op]表示处理到第i位，前缀和为st，是否与上限相等为op的答案
ll dfs(int x,int st,int op){
    if(!x) return (ll)st;
    if(~f[x][st][op]) return f[x][st][op];
    ll res=0;
    int maxx=op?v[x]:K-1;
    for(int i=0;i<=maxx;i++){
        res+=dfs(x-1,st+i*(x-1),op&&(i==maxx));
    }
    return f[x][st][op]=res;
}
int mid;
ll dfs2(int x,int st,int op){
    if(st<0) return 0ll;
    if(!x) return (ll)st;
    if(~d[x][st][op]) return d[x][st][op];
    ll res=0;
    int maxx=op?v[x]:K-1;
    for(int i=0;i<=maxx;i++){
        if(x>=mid) res+=dfs2(x-1,st+i,op&&(i==maxx));
        else res+=dfs2(x-1,st-i,op&&(i==maxx));
    }
    return d[x][st][op]=res;
}
ll solve(ll x){
    ll ans=0ll;
    v.clear();
    v.push_back(-1);
    while(x){
        v.push_back(x%K);
        x/=K;
    }
    memset(f,-1,sizeof(f));
    ans+=dfs(v.size()-1,0,1); //计算将所有位数字都集中到最右端/最低位的最小代价
    for(mid=2;mid<=v.size()-1;mid++){ //枚举最终合并点
        memset(d,-1,sizeof(d));
        ll temp=dfs2(v.size()-1,0,1);
        ans-=temp;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ3598.in","r",stdin);
    cin>>A>>B>>K;
    cout<<solve(B)-solve(A-1);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif
上一篇 下一篇

猜你喜欢

热点阅读