HDOJ 1284 钱币兑换问题

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1284


粗略一看,直接套母函数的模版~~~
结果TLE了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 注意这是TLE的代码
// HDOJ 1284
#include <iostream>
using namespace std;
// Author: Tanky Woo
// www.wutianqi.com
const int _max = 40000; 
 
int c1[_max], c2[_max];   
int main()
{    //int n,i,j,k;
    int nNum;   // 
    int i, j, k;
 
    while(scanf("%d", &nNum) != EOF)
    {
        for(i=0; i<=nNum; ++i) 
        {
            c1[i] = 1;
            c2[i] = 0;
        }
        for(i=2; i<=3; ++i)
        {
 
            for(j=0; j<=nNum; ++j) 
                for(k=0; k+j<=nNum; k+=i)
                {
                    c2[j+k] += c1[j];
                }
            for(j=0; j<=nNum; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        printf("%d\n", c1[nNum]);
    }
    return 0;
}

后来改了下:
500多MS~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
 
int c1[32768], c2[32768] = {0};
int main()
{
    int i, j, k, h;
 
    for (i = 0; i <= 32767; i++)
        c1[i] = 1;
    for (i = 2; i <= 3; i++)
    {
        for (j = 0; j <= 32767; j++)
        {
            for (k = 0; k + j <= 32767; k += i)
            {
                c2[k + j] += c1[j];
            }
        }
        for (h = 0; h <= 32767; h++)
        {
            c1[h] = c2[h];
            c2[h] = 0;
        }
    }
 
    int n;
    while (scanf("%d", &n) != EOF)
        printf("%d\n", c1[n]);
 
    return 0;
}

后来发现这题其实可以不用母函数的:
思路:
直接COPY网上的了。
就是求2x+3y+k=m的问题这时m就可以写成m=6*q+k;
带入上式子 可得到 y=3*q+k/2-3*x/2;
x的取值0-2*q之间的偶数
有1+q中 所以else后面要加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main()
{
    __int64 n,i,j,sum;
    while(scanf("%I64d",&n)==1)
    {
        sum=0;
        for(i=0;i<=n/3;i++)
        {
            sum+=(n-i*3)/2+1;
        }
        printf("%I64d\n",sum);
    }
}

最后一个,还是母函数的思想,但是时间是0MS~~~
AMB教主的代码~~~Orz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
 
int num[32768];
void main()
{
    int n,i;
    num[0]=1;
    for(i=1;i<32768;i++)
        num[i]+=num[i-1];
    for(i=2;i<32768;i++)
        num[i]+=num[i-2];
    for(i=3;i<32768;i++)
        num[i]+=num[i-3];
    while(cin>>n)
        printf("%d\n",num[n]);
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注