NOIP訓練營內部試題-火柴棒(dp)
摘要:
清北學堂NOIP2017屆內部訓練題提供給大家。本題目是比較簡單的動態規劃題。
題目:位運算
(stick)
Time Limit:1000ms Memory Limit:128MB
題目描述
眾所周知的是,火柴棒可以拼成各種各樣的數字。具體可以看下圖:
通過2根火柴棒可以拼出數字「1」,通過5根火柴棒可以拼出數字「2」,以此類推。
現在LYK擁有k根火柴棒,它想將這k根火柴棒恰好用完,並且想知道能拼出的最小和最大的數分別是多少。
輸入格式(http://stick.in)
一個數k。
輸出格式(stick.out)
兩個數,表示最小的數和最大的數。注意這兩個數字不能有前導0。
輸入樣例
15
輸出樣例
108 7111111
數據範圍
對於30%的數據k<=10。
對於60%的數據k<=20。
對於100%的數據1<k<=100。
/*
最大值直接特判一下,最小值用dp解決
dp[i]表示i根火柴能拼出的最小的數字,枚舉該數字末尾的一位是幾
*/
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
long long dp[105];
int f[15],n;
int main()
{
freopen("http://stick.in","r",stdin);
freopen("stick.out","w",stdout);
f[1]=2; f[2]=5; f[3]=5; f[4]=4; f[5]=5;
f[6]=6; f[7]=3; f[8]=7; f[9]=6; f[0]=6;
dp[2]=1; dp[3]=7; dp[4]=4; dp[5]=2; dp[6]=6;dp[7]=8;
for (int i=8; i<=100; i++)
{
dp[i]=dp[i-f[0]]*10;
for (int j=0; j<=9; j++)
if (dp[i-f[j]]!=0)
dp[i]=min(dp[i],dp[i-f[j]]*10+j);
}
cin>>n;
cout<<dp[n]<< ;
if (n%2==1) {cout<<7; n-=3;}
while (n){cout<<1; n-=2;}
return 0;
}
解析:動態規劃
其實第二問非常好像,我們要讓數字最大,就一定要讓位數最大,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,前面的用啥思考一下就能出來.