2013-02-28 12:09:28Morris
[UVA][dp&greedy] 12172 - Matchsticks
Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:
This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
- One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have.
Output
Per testcase:
- One line with the smallest and largest numbers you can create, separated by a single space. Both numbers should be positive and contain no leading zeroes.
Sample Input
4 3 6 7 15
Sample Output
7 7 6 111 8 711 108 7111111
The 2008 ACM Northwestern European Programming Contest
很明顯地，小的要用 dp，大的要用 greedy。
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
scanf("%*d");
long long dp[105] = {};
int i, j;
for(i = 0;i < 105; i++)
dp[i] = 1LL<<60;
dp[2] = 1, dp[3] = 7;
dp[4] = 4, dp[5] = 2;
dp[6] = 6, dp[7] = 8;
int cost[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
for(i = 2; i < 105; i++) {
for(j = 0; j < 10; j++) {
if(i+cost[j] < 105) {
dp[i+cost[j]] = min(dp[i+cost[j]], dp[i]*10+j);
}
}
}
int n;
while(scanf("%d", &n) == 1) {
printf("%lld ", dp[n]);
if(n%2)
putchar('7'), n -= 3;
for(i = n/2-1; i >= 0; i--)
putchar('1');
puts("");
}
return 0;
}
很明顯地，小的要用 dp，大的要用 greedy。
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
scanf("%*d");
long long dp[105] = {};
int i, j;
for(i = 0;i < 105; i++)
dp[i] = 1LL<<60;
dp[2] = 1, dp[3] = 7;
dp[4] = 4, dp[5] = 2;
dp[6] = 6, dp[7] = 8;
int cost[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
for(i = 2; i < 105; i++) {
for(j = 0; j < 10; j++) {
if(i+cost[j] < 105) {
dp[i+cost[j]] = min(dp[i+cost[j]], dp[i]*10+j);
}
}
}
int n;
while(scanf("%d", &n) == 1) {
printf("%lld ", dp[n]);
if(n%2)
putchar('7'), n -= 3;
for(i = n/2-1; i >= 0; i--)
putchar('1');
puts("");
}
return 0;
}