P11229 [CSP-J 2024] 小木棍

_Yonder_ · 2024-11-09 21:16:17 · 题解

我是沙子吗，交了 9 发才过。

你说得对，但是我没想到打表。

可以发现要是没有数字 0 的话，这题就是普通的 dp，于是考虑求出 1\sim 10^5 的不含数字 0 的最大答案。显然不能用字符串存，用大小 10 的数组表示每个数出现几次就行。

求出来后枚举加几个 0，取最大值即可。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
struct node{int c[10];}f[N],u,d;
int T,n,w[10]={6,2,5,5,4,5,6,3,7,6};
inline node Min(node x,node y){
    int lx=0,ly=0,a,b;
    for(int i=0;i<=9;i++) lx+=x.c[i];
    for(int i=0;i<=9;i++) ly+=y.c[i];
    if(lx^ly) return lx<ly?x:y;
    for(int i=9;i;i--) if(x.c[i]) a=i;
    for(int i=9;i;i--) if(y.c[i]) b=i;
    if(a^b) return a<b?x:y;
    for(int i=0;i<=9;i++)
        if(x.c[i]^y.c[i])
            return x.c[i]>y.c[i]?x:y;
    return x;
}inline void put(node x){
    int u=9;
    for(int i=9;i;i--) if(x.c[i]) u=i;
    putchar(u+'0');x.c[u]--;
    for(int i=0;i<=9;i++)
        for(int j=x.c[i];j;j--)
            putchar(i+'0');
    putchar('\n');
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    for(int i=0;i<=9;i++) u.c[i]=1e8;
    for(int i=1;i<N;i++){
        f[i]=u;
        for(int j=1;j<=9;j++)
            if(i-w[j]>=0){
                d=f[i-w[j]];d.c[j]++;
                f[i]=Min(f[i],d);
            }
    }
    while(T--){
        cin>>n;
        if(!n) return 1;
        if(n==1){cout<<-1<<endl;continue;}
        node ans=f[n],now;
        for(int i=1;i*6<n;i++)
            now=f[n-i*6],now.c[0]+=i,ans=Min(ans,now);
        put(ans);
    }
    return 0;
}