[Acwing] 338.计数问题 计数dp

前言

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

思路

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

状态计算 :

• j ! = u j!=u j!=u
  • f [ i ] [ j ] [ u ] + = f [ i − 1 ] [ k ] [ u ] ( k ∈ [ 0 , 9 ] ) f[i][j][u]+=f[i-1][k][u](k \in[0,9]) f[i][j][u]+=f[i−1][k][u](k∈[0,9])
• j = u j=u j=u
  • f [ i ] [ j ] [ u ] + = 1 0 i − 1 + f [ i − 1 ] [ k ] [ u ] ( k ∈ [ 0 , 9 ] ) f[i][j][u]+=10^{i-1}+f[i-1][k][u](k \in[0,9]) f[i][j][u]+=10i−1+f[i−1][k][u](k∈[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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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--)

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

void init(){
	for(int i=0;i