数页码--数位dp

1.板子是板子，但也要灵活运用，比如注意边界条件该返回什么

2.板子tot就是一个需要根据实际情况变化的量

P1836 数页码 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
ll n,k;
int b; 
vector<int> a;
ll dp[60][360];
ll dfs(int pos,int c,bool ismax)///c表示pos前面已经固定的和 
{if(pos==-1){return c;///c记录的就是这种情况的答案和 }if(!ismax&&dp[pos][c]!=-1) return dp[pos][c];int maxn;if(ismax) maxn=a[pos];else maxn=9;ll res=0;///到这里，前面都是板子 for(int i=0;i<=maxn;i++){res+=dfs(pos-1,c+i,ismax&&i==maxn);///将后面的答案累加 }if(!ismax) dp[pos][c]=res;return res;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);b=10;cin>>n;ll x=n;memset(dp,-1,sizeof(dp));while(x){a.push_back(x%10);x/=10;}ll an=dfs(a.size()-1,0,true);cout<<an;return 0;
}