摘要：

清北學堂NOIP2017屆內部訓練題提供給大家。本題目是比較簡單的動態規劃題。

題目：位運算

(stick)

Time Limit:1000ms Memory Limit:128MB

題目描述

眾所周知的是，火柴棒可以拼成各種各樣的數字。具體可以看下圖：

通過2根火柴棒可以拼出數字「1」，通過5根火柴棒可以拼出數字「2」，以此類推。

現在LYK擁有k根火柴棒，它想將這k根火柴棒恰好用完，並且想知道能拼出的最小和最大的數分別是多少。

輸入格式(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("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,前面的用啥思考一下就能出來.

推薦閱讀：

相關文章