● [合集]大家试试做这题～ - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: kaman (天外飞仙), 信区: ACMICPC
标  题: [合集]大家试试做这题～
发信站: 荔园晨风BBS站 (Tue Jun  1 11:06:26 2004), 站内信件

kaman (天外飞仙) 于Wed Apr 14 16:23:30 2004提到：

花了我两个小时，郁闷！posidone你试试用多少时间～

Money Systems

The cows have not only created their own government but they have chosen
to create their own money system. In their own rebellious way, they are
curious about values of coinage. Traditionally, coins come in values
like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin
thrown in for good measure.

The cows want to know how many different ways it is possible to dispense
a certain amount of money using various coin systems. For instance,
using a system of {1, 2, 5, 10, ...} it is possible to create 18 units
several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many
others.

Write a program to compute how many ways to construct a given amount
of money using supplied coinage. It is guaranteed that the total will
fit into both a signed long long (C/C++) and Int64 (Free Pascal).

PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).

The amount money to construct is N (1 <= N <= 10,000). Line 1:  Two
integers, V and N
Lines 2..:  V integers that represent the available coins (no particular
number of integers per line)

SAMPLE INPUT (file money.in)
3 10
1 2 5

OUTPUT FORMAT
A single line containing the total number of ways to construct N money
units using V coins.
SAMPLE OUTPUT (file money.out)
10

测试数据：

kaman (天外飞仙) 于Wed Apr 14 16:30:40 2004提到：

极典型的动态规划～～

posidone (海王波赛冬) 于Wed Apr 14 18:32:07 2004提到：

6：00开始看这题，
半个钟就搞定了。呵呵
把那组测试数据的输出给我。

kaman (天外飞仙) 于Wed Apr 14 19:58:21 2004提到：

17 500
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
answer:18390132498
8 10000
1 2 3 4 5 6 20 25
answer:5639936605407277702
这两个对了就行

kaman (天外飞仙) 于Wed Apr 14 22:56:52 2004提到：

把你的程序贴上来

posidone (海王波赛冬) 于Wed Apr 14 23:04:25 2004提到：

#include<stdio.h>
#include<string.h>

int a[100];
_int64 b[10001][25];

int n;
_int64 search(int k,int t)
{
        int i;
        _int64 u;

        if(k==0) return 1;
        if(b[k][t]!=-1) return b[k][t];
        u=0;
        for(i=t;i<n;i++)
        {
                if(k-a[i]>=0) u+=search(k-a[i],i);
        }

        b[k][t]=u;
        return u;
}
void main()
{
        int k,i;
        _int64 u;

        freopen("money.in","r",stdin);
        freopen("money.out","w",stdout);

        while(1)
        {
          scanf("%d %d",&n,&k);
          if(n==0&&k==0) break;
          for(i=0;i<n;i++)
          {
                scanf("%d",&a[i]);
          }

          memset(b,-1,sizeof(b));

          u=search(k,0);
          printf("%I64d\n",u);
        }
}

kaman (天外飞仙) 于Wed Apr 14 23:06:58 2004提到：

看看这一个，gcc下通过
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAXTOTAL 10000

long long nway[MAXTOTAL+1];

void
main(void)
{
        FILE *fin, *fout;
        int i, j, n, v, c;

        fin = fopen("money.in", "r");
        fout = fopen("money.out", "w");
        assert(fin != NULL && fout != NULL);

        fscanf(fin, "%d %d", &v, &n);

        nway[0] = 1;
        for(i=0; i<v; i++) {
                fscanf(fin, "%d", &c);

                for(j=c; j<=n; j++)
                        nway[j] += nway[j-c];
        }

        fprintf(fout, "%lld\n", nway[n]);
}

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店