[数据结构与算法][Acwing] 338.计数问题 计数dp

前言

可以说是基础课最难理解的一个了
传送门 :

思路

状态表示 : $f[i][j][u]$ 一共有$i$位,最高位是$j$ 中$u$的个数

状态计算 :

• $j!=u$
  • $f[i][j][u]+=f[i?1][k][u](k\in [0,9])$
• $j=u$
  • $f[i][j][u]+=10^{i?1}+f[i?1][k][u](k\in [0,9])$

Mycode

// Problem: 计数问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/340/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
int f[11][10][10];
int l,r;

void init(){
	for(int i=0;i<=9;i++) f[1][i][i] = 1;
	for(int i=2;i<=10;i++)
		for(int j=0;j<=9;j++)
			for(int u =0 ;u<=9;u++){
				if(u == j) f[i][j][u] += pow(10,i-1);
				for(int k=0;k<=9;k++)
				f[i][j][u] += f[i-1][k][u];
			} 
}
int dp(int n,int u){
	if(!n) return u?0:1;
	vector<int> num;
	
	while(n) num.pb(n%10),n/=10;
	
	int ans = 0  ,last = 0 ;
	for(int i= num.size()-1;i>=0;i--){
		int x = num[i];
		for(int j = (i == num.size()-1);j<x;j++){
			ans +=f[i+1][j][u];
		}
		
		ans += x*last*pow(10,i);
		if(x == u) last++;
		if(!i) ans+=last;
	}
	
	for(int i=1;i<num.size();i++)
		for(int j=i!=1;j<=9;j++)
		ans += f[i][j][u];
		
	return ans;
	
}
void solve(){
	if(l>r)swap(l,r);
	for(int i=0;i<=9;i++){
		cout<<dp(r,i)  - dp(l-1,i)<<" ";
	}
	cout<<endl;
	
}

int main(){
	init();
	
    //int t;cin>>t;while(t--)
    while(cin>>l>>r,l||r)
    solve();
    return 0 ;
}