背包与构造

题目：给定一个数，，求它最少能够用多少个包括字符串"61"的数字来表示，并输出这些数。

 

分析：对于大于6161的不论什么一个整数，都有例如以下表示

 

    

 

     对于小于1616的数，直接背包就可以。

 

代码：

#include <string.h>
#include <iostream>
#include <stdio.h>

using namespace std;
typedef long long LL;
const int N = 10005;
const int INF = 0x3f3f3f3f;

int dp[N];
int pre[N];
int v[N];

bool check(LL n)
{
    int a[20];
    int cnt = 0;
    while(n)
    {
        a[cnt++] = n % 10;
        n /= 10;
    }
    for(int i = 0;i < cnt-1;i++)
        if(a[i] == 1 && a[i+1] == 6)
            return true;
    return false;
}

void ouput(int n)
{
    if(pre[n] != 0) ouput(pre[n]);
    printf(" %d",n - pre[n]);
}

int main()
{
    int T;
    LL n;
    scanf("%d",&T);
    int num = 0;
    for(int i = 1;i <= 6161;i++)
        if(check(i))
            v[num++] = i;
    for(int i = 0;i < N;i++)
        dp[i] = INF;
    dp[0] = 0;
    pre[0] = -1;
    for(int i = 1;i < N;i++)
    {
        for(int j = 0;j < num && v[j] <= i;j++)
        {
            if(dp[i] > dp[i-v[j]] + 1)
            {
                dp[i] = dp[i-v[j]] + 1;
                pre[i] = i - v[j];
            }
        }
    }
    while(T--)
    {
        scanf("%lld",&n);
        if(check(n))
        {
            printf("1 %lld
",n);
            continue;
        }
        if(n >= 6161)
        {
            LL ans1 = 61;
            LL ans2 = 6100;
            n -= 6161;
            ans2 += n % 100;
            ans1 += (n / 100) * 100;
            printf("2 %lld %lld
",ans1,ans2);
            continue;
        }
        if(dp[n] == INF)
        {
            printf("0
");
            continue;
        }
        printf("%d",dp[n]);
        ouput(n);
        printf("
");
    }
    return 0;
}