【题目记录】——DP（长期更新）

拼搏现实的明天。 2022-09-11 06:13 139阅读 0赞

### 文章目录 ###

*  已整理
 *  未整理
 *   *  P2602 数字计数 数位DP
     *  POJ 2282 The Counting Problem 数位DP
     *  HDU3555 Bomb 数位DP
     *  POJ3252 Round Numbers 数位DP
     *  POJ 3311 Hie with the Pie 状态压缩DP

# 已整理 #

[A Intelligent Warehouse][] 线性DP  
【题目记录】——2020ICPC·小米 网络选拔赛第一场(重现赛)  
[HDU2089 不要62][HDU2089 _62] 数位DP  
【算法与数据结构】——数位DP（1）  
[洛谷1174][1174] DP  
【题目记录】——2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛  
[Increasing Subsequence][] DP  
【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（4）  
[POJ 3260 The Fewest Coins][]  
【题目记录】——POJ 3260 The Fewest Coins 混合背包  
[1009 Rise in Price][] DP  
【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（3）  
[F题目地址][F] 数位DP  
【题目记录】——2021牛客暑期多校训练营1

# 未整理 #

## P2602 数字计数 数位DP ##

[P2602 数字计数][P2602]

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    ll dp[14][10][10]; //dp[i][j][k] i位数字第1位是j时,k出现的次数
    ll res[2][10];
    ll qpow(int a, int b)
    { 
        ll ans = 1;
        while(b)
        { 
            if(b%2)
            { 
                ans*=a;
            }
            a*=a;
            b>>=1;
        }
        return ans;
    }
    void init()
    { 
        for(int i = 0;i <= 9;i++)
        { 
            dp[1][i][i] = 1;
        }
        for(int i = 2;i <= 12;i++)
        { 
            for(int j = 0;j <= 9;j++)
            { 
                for(int k = 0;k <= 9;k++)
                { 
                    for(int jj = 0;jj <=9;jj++)
                    { 
                        dp[i][j][k]+=dp[i-1][jj][k];
                    }
                }
                dp[i][j][j]+=qpow(10,i-1);
            }
        }
    
    }
    void cal(ll x,int p)//[0,x)的k的出现次数
    { 
        int num[14];
        int cnt = 0;
        ll t = x;
        while(x)
        { 
            num[++cnt]=x%10;
            x/=10;
        }
        //从低位向高位枚举,便于判断前导零的情况
        for(int i=1;i<cnt;i++)       //位数比x小的，一定能够满足条件
        { 
            for(int j=1;j<=9;j++)    //不能有前导零
            { 
                for(int k=0;k<=9;k++)
                { 
                    res[p][k]+=dp[i][j][k];
                }
            }
        }
        //最高位小于num[i]的时候，也能满足条件
        for(int i = 1;i<num[cnt];i++)
        { 
            for(int k = 0;k <= 9;k++)
            { 
                res[p][k]+=dp[cnt][i][k];
            }
        }
        //用到数位DP的思想
        for(int i = cnt - 1;i>=1;i--)
        { 
            for(int j = 0;j < num[i];j++)
            { 
                for(int k = 0;k < 10;k++)
                { 
                    res[p][k]+=dp[i][j][k];
                }
            }
            //num[i+1]出现了t % qpow(10,i)+1次
            res[p][num[i+1]] += t % qpow(10,i)+1;
        }
        //特判n为1的情况
        if(cnt)
        res[p][num[1]]+=1;
    }
    void solve()
    { 
        init();
        ll n,m;
        scanf("%lld%lld",&n,&m);
        cal(n-1,0);
        cal(m,1);
        for(int i = 0;i<10;i++)
        { 
            printf("%lld ",res[1][i]-res[0][i]);
        }
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t = 1;
    // int t;
    // scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

## POJ 2282 The Counting Problem 数位DP ##

[POJ 2282 The Counting Problem][]  
题意：跟[P2602 \[ZJOI2010\]数字计数][P2602]题目基本一样，求一个区间内，0-9每个数字出现的次数，只是输入方式不一样，前面给出了预处理的解法，这里给出一个记忆化搜索的解法:

//#include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <stack>
    #include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 20;
    ll res[2][10];
    int dig[N];
    ll dp[N][10][N];
    //dp[i][j][k]表示第i个位置，j是要统计的值，k表示到目前j出现的次数
    int dfs(int pos, int val, int cnt, bool lead, bool limit)
    { 
        if (pos==0)
        { 
            return cnt;
        }
        if(!limit&&!lead&&dp[pos][val][cnt])
        { 
            return dp[pos][val][cnt];
        }
        int len = limit?dig[pos]:9;
        int t = 0;
        ll ans = 0;
        for(int i = 0;i <= len;i++)
        { 
            if(val!=i) t = cnt;
            else
            { 
                if(lead&&val==0)
                { 
                    t=0;
                }
                else
                { 
                    t = cnt + 1;
                }
            }
            ans+=dfs(pos-1,val,t,lead&&i==0,limit&&i==len);
        }
        if(!limit&&!lead)
        { 
            dp[pos][val][cnt] = ans;
        }
        return ans;
    }
    void cal(int x, int p)
    { 
        int cnt = 0;
        while(x)
        { 
            dig[++cnt]=x%10;
            x/=10;
        }
        for(int i = 0;i < 10;i++)
        { 
            res[p][i] = dfs(cnt, i, 0, 1, 1);
        }
    }
    void solve()
    { 
        int n, m;
        while(scanf("%d%d",&n,&m)&&n)
        { 
            if(n > m)
            { 
                swap(n,m);
            }
            cal(n-1,0);
            cal(m,1);
            for(int i = 0;i < 10;i++)
            { 
                printf("%lld ",res[1][i]-res[0][i]);
            }
            printf("\n");
        }
    }
    int main()
    { 
    	freopen("in.txt","r",stdin);
    	freopen("out.txt","w",stdout);
    	int t = 1;
    // int t;
    // scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

## HDU3555 Bomb 数位DP ##

[HDU3555 Bomb][]  
题意：找出1到N中含有49的数的数量。  
思路：典型数位dp  
跟 [HDU2089 不要62][HDU2089 _62] 基本一样，这个是找出不含62和4的数的个数，本题目是找到含有49的数的个数，其实可以看做找出不含49的数的个数，然后让总数量减去不含49的数的个数。

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    ll dp[25][10];
    ll qpow(ll a,int b)
    { 
        ll ans = 1;
        while(b)
        { 
            if(b&1)
            { 
                ans*=a;
            }
            a*=a;
            b>>=1;
        }
        return ans;
    }
    void init()
    { 
        for(int i = 0;i < 10;i++)
        { 
            dp[1][i] = 1;
        }
        for(int i = 2;i <= 24;i++)
        { 
            for(int j = 0;j <= 9;j++)
            { 
                for(int k = 0;k <= 9;k++)
                { 
                    if(j==4&&k==9)
                    { }
                    else
                    { 
                        dp[i][j]+=dp[i-1][k];
                    }
                }
            }
        }
    }
    ll cal(ll x)//[0,x]不含49的数的个数
    { 
        int cnt=0;
        int num[25];
        while(x)
        { 
            num[++cnt]=x%10;
            x/=10;
        }
        num[cnt+1]=0;
        ll ans = 0;
        for(int i = cnt;i>=1;i--)
        { 
            for(int j = 0;j < num[i];j++)
            { 
                ans+=dp[i][j];
            }
            if(num[i]==9&&num[i+1]==4)
            { 
                ans--;
                break;
            }
        }
        return ans;
    }
    void solve()
    { 
    	ll n;
    	scanf("%lld",&n);
        printf("%lld\n",n-cal(n));
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
        init();
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

## POJ3252 Round Numbers 数位DP ##

[POJ3252 Round Numbers][]  
题意：如果一个正整数的二进制形式0的个数大于或等于1的个数。则称其为Round Nubers。给出一个区间，统计区间内Round Numbers的个数。

//#include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <stack>
    #include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    int dp[100][100][100];
    int dig[100];
    int dfs(int pos, int num0, int num1, bool lead, bool limit)
    { 
        if(pos==-1) return num0>=num1;
        if(!limit&&dp[pos][num0][num1])
        { 
            return dp[pos][num0][num1];
        }
        int len = limit?dig[pos]:1;
        int ans = 0;
        for(int i = 0;i <= len;i++)
        { 
            if(lead&&!i)//前导零
            { 
                ans += dfs(pos-1,0,0,1,limit&&i==len);
            }
            else
            { 
                ans += dfs(pos-1,num0+(i==0),num1+(i==1),0,limit&&i==len);
            }
        }
        if(!limit)
        { 
            dp[pos][num0][num1]=ans;
        }
        return ans;
    }
    int cal(int x)
    { 
        int pos = 0;
        while(x)
        { 
            dig[pos++]=x%2;
            x>>=1;
        }
        return dfs(pos-1,0,0,1,1);
    }
    void solve()
    { 
        int n, m;
        scanf("%d%d",&n, &m);
        printf("%d\n",cal(m)-cal(n-1));
    // printf("%d\n",cal(m));
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t = 1;
    // int t;
    // scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

## POJ 3311 Hie with the Pie 状态压缩DP ##

[POJ 3311 Hie with the Pie][]  
题意：旅行商变形，司机从披萨店出发，走最短的路线运送所有货物，途中可能经过相同的地点或者披萨店不止一次。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <stack>
    #include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 12;
    int g[N][N];
    ll dp[1<<N][N];
    void update(int n)
    { 
        for(int i = 0; i < n+1; i++)
            for(int j = 0; j < n+1; j++)
                for(int k = 0; k < n+1; k++)
                { 
                    g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
                }
    }
    
    void solve()
    { 
        int n;
        while(scanf("%d",&n)&&n)
        { 
            memset(dp,INF,sizeof(dp));
    
            for(int i = 0; i < n+1; i++)
                for(int j = 0; j < n+1; j++)
                { 
                    scanf("%d",&g[i][j]);
                }
            update(n);
            dp[(1<<(1+n))-1][0]=0;
            for(int S = (1<<(n+1)) -2;S>=0;S--)
                for(int j = 0;j <= n;j++)
                    for(int k = 0;k <= n;k++)
                    { 
                        if(!(S>>j & 1)&&j!=0)continue;
                        if(!(S>>k & 1)&&dp[S][j]>dp[S|(1<<k)][k]+g[j][k])
                        { 
                            dp[S][j]=dp[S|(1<<k)][k]+g[j][k];
                        }
                    }
            printf("%lld\n",dp[0][0]);
        }
    }
    int main()
    { 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
        int t = 1;
    // int t;
    // scanf("%d",&t);
        while(t--)
        { 
            solve();
        }
        return 0;
    }

[A Intelligent Warehouse]: https://ac.nowcoder.com/acm/contest/7501/A
[HDU2089 _62]: https://acm.hdu.edu.cn/showproblem.php?pid=2089
[1174]: https://www.luogu.com.cn/problem/P1174
[Increasing Subsequence]: https://acm.hdu.edu.cn/showproblem.php?pid=6991
[POJ 3260 The Fewest Coins]: https://link.csdn.net/?target=http%3A%2F%2Fpoj.org%2Fproblem%3Fid%3D3260
[1009 Rise in Price]: https://acm.hdu.edu.cn/showproblem.php?pid=6981
[F]: https://ac.nowcoder.com/acm/contest/11166/F
[P2602]: https://www.luogu.com.cn/problem/P2602
[POJ 2282 The Counting Problem]: http://poj.org/problem?id=2282
[HDU3555 Bomb]: https://acm.hdu.edu.cn/showproblem.php?pid=3555
[POJ3252 Round Numbers]: http://poj.org/problem?id=3252
[POJ 3311 Hie with the Pie]: http://poj.org/problem?id=3311