Solve

USACO 2.3.4 Money

题目解答

这道题目有必要解释一下我写的DP，a[j]=a[j]+a[j-k] (0<=j<=n)，其中k为当前面值，思想是这样的：f[j]是用j面值可组成钱的方案数，事实上就是先降维后记忆化搜索的背包，原来的方程是：f[i,j]=f[i-1,j]+f[i,j-k]因为选中k后还可以再次选择(01背包只能选一次)所以第二个式子是i而不是i-1。

运行结果

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.000 secs, 288 KB]
Test 2: TEST OK [0.011 secs, 288 KB]
Test 3: TEST OK [0.000 secs, 284 KB]
Test 4: TEST OK [0.000 secs, 284 KB]
Test 5: TEST OK [0.000 secs, 288 KB]
Test 6: TEST OK [0.000 secs, 284 KB]
Test 7: TEST OK [0.000 secs, 284 KB]
Test 8: TEST OK [0.000 secs, 284 KB]
Test 9: TEST OK [0.011 secs, 284 KB]
Test 10: TEST OK [0.000 secs, 288 KB]
Test 11: TEST OK [0.000 secs, 284 KB]
Test 12: TEST OK [0.000 secs, 288 KB]
Test 13: TEST OK [0.000 secs, 288 KB]

All tests OK.
Your program (‘money’) produced all correct answers! This is your
submission #1 for this problem. Congratulations!

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
program money;
var v,n,i,j,k:integer;
  a:array[0..10000]of int64;
begin
  assign(input,'money.in');
  reset(input);
  assign(output,'money.out');
  rewrite(output);
  readln(v,n);
  a[0]:=1;

  for i:=1 to v do
  begin
    read(k);
    for j:=k to n do
      a[j]:=a[j]+a[j-k];
  end;

  writeln(a[n]);
  close(input);
  close(output);
end.

后记

本文是原新浪博客的移植，附：全部USACO题目解答。