加载中…
个人资料
sacredfantasy
sacredfantasy
  • 博客等级:
  • 博客积分:0
  • 博客访问:3,313
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

usaco 2.3.4 money

(2009-04-27 17:59:40)
标签:

usaco

2.3.4

money

杂谈

分类: OI题解

很简单也很经典,一维的程序贴上:

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!

这道题目有必要解释一下我写的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后还可以再次选择(背包只能选一次)所以第二个式子是i而不是i-1;

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.

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
后一篇:usaco 2.4.1 ttwo
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    后一篇 >usaco 2.4.1 ttwo
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有