UVa 11375 Matches:DP&高精度

UVa 11375 Matches:DP&高精度2014-10-02 csdn博客 synapse7

11375 - Matches

Time limit: 2.000 seconds

We can make digits with matches as shown below:

Given N matches, 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 integer N （1 ≤ N ≤ 2000）.

Output

For each N, output the number of different （non-negative） numbers representable if you have N matches.

Sample Input

Sample Output

简单DP。

完整代码：

/*0.076s*/#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2001;// 本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45373.htmconst 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;}