P11229 [CSP-J 2024] 小木棍（民间数据）dp题解
题外话
考场上这题花了一小时才调出来，终于把大样例过了，写篇题解庆祝一下🎉
思路
你们别说dp不能AC，我倒是成功把大样例过了，这也证实了我对这题的第一感觉。
第一步（MLE 0pts）
先设出状态转移数组：
node f[100010];//f[i]表示用i根火柴棒能拼成的最小数字
（node是我已经写好的100000位高精度）
这样肯定会 MLE ，而且状态转移过程中还可能 TLE
再写出状态转移方程：
f[j]=min(f[j],f[j-a[i]]*10+i);//a[i]表示i这个数字所需的火柴棒根数，下同
数位dp?继续往下看吧
第二步核心优化(100pts)
就直接核心优化了？？？
是的，就这么简单。可是为什么这么多人想不到呢？
带入一个情景吧
这个东西一年级都知道
给你几个数字，请问按什么顺序排才能使拼出的数最小呢？（
是不是这样：
1.找出最小的不为0数字作为首位
2.从小到大排列剩下的数字核心结论：只要知道0~9每个数字的个数，就能确定一个 唯一 的数字
所以高精度就变成了：
struct node{ int a[20],len; }f[100017],t;//f[i]:用i根火柴能品出的最小数字（a[i]:这个数字有多少个i (0 ≤i ≤ 9) ）那么又出现了一个难点，这样一来，如何比较两个数的大小呢？
比较两数大小
其实很简单，就和刚刚带入的情境差不多：
1.比较两数的长度
2.比较两数的最小非0数字
3.从小到大比较剩下的数字
（输出参考刚刚带入的情境）
Code(有注释)
#include<bits/stdc++.h>
#define N 100000
using namespace std;
struct node{
int a[20],len;
}f[100017],t;//f[i]:用i根火柴能品出的最小数字（a[i]:这个数字有多少个i (0 ≤i < 10) ）
int ds[20]={6,2,5,5,4,5,6,3,7,6};
void print(node x){
if(x.len==-1){//如果这个状态不存在
cout<<"-1\n";
return ;
}
int l=1;
while(x.a[l]==0)++l;
cout<<l;
//输出的第一步
x.a[l]--;
for(int i=0;i<10;++i){//输出的第二步
while(x.a[i]--)cout<<i;
}
cout<<'\n';
}
int main(){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for(int i=1;i<=N;++i){
f[i].len=-1;
}
f[2]={{0,1},1};
f[3]={{0,0,0,0,0,0,0,1},1};
f[4]={{0,0,0,0,1},1};
f[5]={{0,0,1},1};
f[6]={{0,0,0,0,0,0,1},1};
f[7]={{0,0,0,0,0,0,0,0,1},1};
//手动打出使用2、3、4、5、6、7根火柴棒所拼出的数字
for(int i=0;i<10;++i){
for(int j=2;j<=N;++j){
if(f[j].len==-1)continue;//如果这个状态不存在
t=f[j];
t.a[i]++,t.len++;
if(f[j+ds[i]].len==-1)f[j+ds[i]]=t;//如果这个状态不存在
if(f[j+ds[i]].len==t.len){//比较的第一步
int l=1;
while(f[j+ds[i]].a[l]==0&&t.a[l]==0)++l;
if(f[j+ds[i]].a[l]==0){
f[j+ds[i]]=t;
continue;
}
//比较的第二步
else if(t.a[l]>0){
for(int k=0;k<10;++k){//比较的第三步
if(t.a[k]>f[j+ds[i]].a[k]){
f[j+ds[i]]=t;
}
if(t.a[k]!=f[j+ds[i]].a[k]){
break;
}
}
}
}
else if(f[j+ds[i]].len>t.len){//比较的第一步
f[j+ds[i]]=t;
}
}
}
int t,n;
cin>>t;
while(t--){
cin>>n;
print(f[n]);
}
return 0;
}