UVa 11375 Matches (DP&高精度)
11375 - MatchesTime limit: 2.000 secondshttp://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2370We can make digits with matches as shown below:Given...
11375 - Matches
Time limit: 2.000 seconds
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2370
We can make digits with matches as shown below:
GivenNmatches, find the number of different numbers representable using the matches. We shall only make numbers greater than or equal to 0, so no negative signs should be used. For instance, if you have 3 matches, then you can only make the numbers 1 or 7. If you have 4 matches, then you can make the numbers 1, 4, 7 or 11. Note that leading zeros are not allowed (e.g. 001, 042, etc. are illegal). Numbers such as 0, 20, 101 etc. are permitted, though.
Input
Input contains no more than 100 lines. Each line contains one integerN(1 ≤N≤ 2000).
Output
For eachN, output the number of different (non-negative) numbers representable if you haveNmatches.
Sample Input
3 4
Sample Output
2 4
简单DP。
完整代码:
/*0.076s*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2001;
const int c[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /// c[i]表示数字i需要的火柴数
struct node
{
int p[500], len;
node()
{
memset(p, 0, sizeof(p));
len = 0;
}
node(int a)
{
p[0] = a;
len = 1;
}
node operator + (const node& a) const
{
node b;
b.len = max(len, a.len);
for (int i = 0; i < b.len; i++)
{
b.p[i] += p[i] + a.p[i];
b.p[i + 1] = b.p[i] / 10;
b.p[i] %= 10;
}
if (b.p[b.len] > 0) b.len++;
return b;
}
node operator += (const node& a)
{
*this = *this + a;
return *this;
}
void out()
{
if (len == 0) putchar('0');
else
{
for (int i = len - 1; i >= 0; i--)
printf("%d", p[i]);
}
putchar(10);
}
} d[maxn];
int main()
{
int i, j, n;
d[0] = node(1);
for (i = 0; i < maxn; ++i)
for (j = 0; j < 10; ++j)
if (i + c[j] < maxn && (i || j))
d[i + c[j]] += d[i];
d[6] += node(1);
for (i = 2; i < maxn; ++i) d[i] += d[i - 1];
while (~scanf("%d", &n))
d[n].out();
return 0;
}
更多推荐
所有评论(0)