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题目解答