UVa 11375 Matches:DP&高精度

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:

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

3
4

Sample Output

2
4

简单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.htm
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;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， const
， node
， numbers
， len
matches
gb11375、，以便于您获取更多的相关知识。