两个 100% -1 con 最大的 com 数据 pre namespace
题目描述
众所周知的是,火柴棒可以拼成各种各样的数字。具体可以看下图:
通过2根火柴棒可以拼出数字“1”,通过5根火柴棒可以拼出数字“2”,以此类推。
现在LYK拥有k根火柴棒,它想将这k根火柴棒恰好用完,并且想知道能拼出的最小和最大的数分别是多少。
输入格式(stick.in)
一个数k。
输出格式(stick.out)
两个数,表示最小的数和最大的数。注意这两个数字不能有前导0。
输入样例
15
输出样例
108 7111111
数据范围
对于30%的数据k<=10。
对于60%的数据k<=20。
对于100%的数据1
分析:老师说有这道图片的题都很弱......
其实第二问非常好像,我们要让数字最大,就一定要让位数最大,1的火柴棒数量是最少的,我们放尽量多的1,因为k根火柴棒必须要用完,所以如果k是奇数就要放一个7,只花3根火柴棒,是最优的.
对于第一问,考虑dp,设f[i]为用i根火柴棒的最小的数,那么f[i] = min{f[i - b[j]] +j},b[j]为数字j用的火柴棒数,开个long long就能解决了,当时我怕k=100最多有50位开不下,于是用了结构体存f数组.当然,贪心也可以做,后面若干位用8,前面的用啥思考一下就能出来.
- #include <bits/stdc++.h>
- using namespace std;
- const long long inf = 100000000000000000;
- struct node
- {
- long long v,tot;
- int shu[210];
- }f[210];
- int k,a[20],b[20],sum1,sum2;
- void init()
- {
- for (int i = 0; i <= 9; i++)
- a[i] = i;
- b[0] = 6;
- b[1] = 2;
- b[2] = 5;
- b[3] = 5;
- b[4] = 4;
- b[5] = 5;
- b[6] = 6;
- b[7] = 3;
- b[8] = 7;
- b[9] = 6;
- }
- int main()
- {
- freopen("stick.in","r",stdin);
- freopen("stick.out","w",stdout);
- init();
- scanf("%d",&k);
- for (int i = 1; i <= k; i++)
- {
- f[i].v = inf;
- f[i].tot = 0;
- }
- f[0].v = 0;
- f[0].tot = 0;
- for (int i = 1; i <= k; i++)
- for (int j = 0; j <= 9; j++)
- if (i >= b[j])
- {
- if (i == b[j] && j == 0)
- continue;
- //f[i] = min(f[i],f[i - b[j]] * 10 + a[j]);
- if (f[i].v > f[i - b[j]].v * 10 + a[j])
- {
- f[i] = f[i - b[j]];
- f[i].v = f[i - b[j]].v * 10 + a[j];
- f[i].shu[++f[i].tot] = j;
- }
- }
- for (int i = 1; i <= f[k].tot; i++)
- printf("%d",f[k].shu[i]);
- printf(" ");
- sum1 = k % 2;
- sum2 = (k - sum1 * 3) / 2;
- for (int i = 1; i <= sum1; i++)
- printf("7");
- for (int i = 1; i <= sum2; i++)
- printf("1");
- printf("\n");
- return 0;
- }
清北学堂模拟赛d1t2 火柴棒 (stick)
来源: http://www.bubuko.com/infodetail-2333849.html