首页 > 代码库 > 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