首页 > 代码库 > usaco-2.3-money-pass
usaco-2.3-money-pass
呵呵,这又是一个动态规划问题,d(j)=d(j-vv[i])+d(j)
/*ID: qq104801LANG: C++TASK: money*/#include <iostream>#include <fstream>#include <string>#include <vector>#include <cstdio>#include <algorithm>using namespace std;int N,V;vector<int> vv;long long d[10001];void test(){ freopen("money.in","r",stdin); freopen("money.out","w",stdout); cin>>V>>N; int t; for(int i=0;i<V;i++) { cin>>t; vv.push_back(t); } d[0]=1; for(int i=0;i<V;i++) for(int j=vv[i];j<=N;j++) if (j>=vv[i]) d[j]=d[j-vv[i]]+d[j]; cout<<d[N]<<endl; }int main () { test(); return 0;}
test data:
USER: cn tom [qq104801]TASK: moneyLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.008 secs, 3584 KB] Test 2: TEST OK [0.003 secs, 3584 KB] Test 3: TEST OK [0.003 secs, 3584 KB] Test 4: TEST OK [0.003 secs, 3584 KB] Test 5: TEST OK [0.003 secs, 3584 KB] Test 6: TEST OK [0.005 secs, 3584 KB] Test 7: TEST OK [0.008 secs, 3584 KB] Test 8: TEST OK [0.005 secs, 3584 KB] Test 9: TEST OK [0.005 secs, 3584 KB] Test 10: TEST OK [0.005 secs, 3584 KB] Test 11: TEST OK [0.005 secs, 3584 KB] Test 12: TEST OK [0.008 secs, 3584 KB] Test 13: TEST OK [0.011 secs, 3584 KB]All tests OK.YOUR PROGRAM (‘money‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----1 11------- test 2 ----3 101 2 5------- test 3 ----10 1001 2 3 4 5 6 7 8 9 10------- test 4 ----25 100025000250002500025000250002500025000250002500025000250002500025000250002500025000250002500025000250002500025000250002500025------- test 5 ----25 999925000250002500025000250002500025000250002500025000250002500025000250002500025000250002500025000250002500025000250002500026------- test 6 ----25 99993461309821090165671177595641529481126900445583571287984921360541267212463504771191441719039851214------- test 7 ----25 99978434639165338765457215225242412746135644634771759474056104861231757596411373094671586927196313563------- test 8 ----25 10025242322212019181716151413121110987654321------- test 9 ----25 10037363534333231302928272625242322212019181716151413------- test 10 ----5 100005 8 13 21 34------- test 11 ----17 50011 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27------- test 12 ----8 100001 2 3 4 5 6 20 25------- test 13 ----17 200011 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27Keep up the good work!Thanks for your submission!
usaco-2.3-money-pass
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。