小信拼数字

yejingrun2010 · 2023-01-20 20:09:59 · 个人记录

题目：

小信有n根木棍，他想拼出只包含给定的m种数字中的至少一种数字的数字串。

已知数字1,2,3,4,5,6,7,8,9分别需要2,5,5,4,5,6,3,7,6根火柴。要求n根木棍全部都用完且拼成的数字最大，输出这个数字。保证答案存在。

思路：

我们用普通的肯定会T。

所以，我们得换种思路。

前面我们用优先队列；后面我们用普通的。复杂度O（n）

代码：

#include<bits/stdc++.h>
using namespace std;
vector<long long>v;
long long w[10]={0,2,5,5,4,5,6,3,7,6},n,m,dp[10005],x,y,f[10005];
bool cmp(long long a,long long b){
    return w[a]<w[b]; 
}
bool cmp2(long long a,long long b){
    return a>b; 
} 
int main(){
    scanf("%lld%lld",&n,&m);
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(long long i=1;i<=m;i++){
        scanf("%lld",&x);
        v.push_back(x); 
    } 
     sort(v.begin(),v.end(),cmp);
    for(long long i=0;i<m;i++){
        f[w[v[i]]]=max(f[w[v[i]]],(long long)1);
        for(long long j=f[w[v[i]]]+1;j<=n;j++) if(f[j-w[v[i]]]>0) f[j]=max(f[j],f[j-w[v[i]]]+1);
    }
    y=n;
    sort(v.begin(),v.end(),cmp2);
    while(y) for(long long i=0;i<m;i++) if(y-w[v[i]]+1>=0) if(y-w[v[i]]==0||f[y-w[v[i]]]>0) if(f[y]==f[y-w[v[i]]]+1){
        printf("%lld",v[i]); 
        y-=w[v[i]];
        break;
    }
    return 0;
}