Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

LightOJ - 1232

By: a guest on Aug 8th, 2012  |  syntax: C++  |  size: 2.31 KB  |  hits: 12  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cctype>
  4. #include <cmath>
  5. #include <complex>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <ctime>
  10. #include <deque>
  11. #include <fstream>
  12. #include <iostream>
  13. #include <list>
  14. #include <map>
  15. #include <memory>
  16. #include <queue>
  17. #include <set>
  18. #include <sstream>
  19. #include <stack>
  20. #include <string>
  21. #include <utility>
  22. #include <vector>
  23. #include <iomanip>
  24.  
  25. /*** typedef ***/
  26.  
  27. #define MEMSET_INF 127
  28. #define MEMSET_HALF_INF 63
  29. #define stream istringstream
  30. #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
  31. #define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
  32. #define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
  33. #define INF (1<<30)
  34. #define PI acos(-1.0)
  35. #define pb push_back
  36. #define ppb pop_back
  37. #define all(x) x.begin(),x.end()
  38. #define mem(x,y) memset(x,y,sizeof(x))
  39. #define memsp(x) mem(x,MEMSET_INF)
  40. #define memdp(x) mem(x,-1)
  41. #define memca(x) mem(x,0)
  42. #define eps 1e-9
  43. #define pii pair<int,int>
  44. #define pmp make_pair
  45. #define ft first
  46. #define sd second
  47. #define pf printf
  48. #define sf scanf
  49. #define vi vector<int>
  50. #define vpii vector<pii>
  51. #define si set<int>
  52. #define msi map<string , int >
  53. typedef long long i64;
  54. typedef unsigned long long ui64;
  55.  
  56. /** function **/
  57.  
  58. #define SDi(x) sf("%d",&x)
  59. #define SDl(x) sf("%lld",&x)
  60. #define SDs(x) sf("%s",x)
  61. #define SD2(x,y) sf("%d%d",&x,&y)
  62. #define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)
  63.  
  64. using namespace std;
  65.  
  66. #define READ(f) freopen(f, "r", stdin)
  67. #define WRITE(f) freopen(f, "w", stdout)
  68. #define mod 100000007
  69.  
  70. int coin[60],limit[60];
  71. int make;
  72. int con;
  73. long long dp[10010][110];
  74. bool vis[10010][110];
  75. int call(int amount,int idx)
  76. {
  77.         if(idx>con)
  78.         {
  79.                 if(amount==make) return 1;
  80.                 return 0;
  81.         }
  82.  
  83.         if(amount>make) return 0;
  84.         if(amount==make) return 1;
  85.  
  86.         if(vis[amount][idx]) return dp[amount][idx];
  87.         else vis[amount][idx]=true;
  88.         int ret1=0,ret2=0;
  89.  
  90.     ret1+=call(amount+coin[idx],idx)%mod;
  91.  
  92.         ret2+=call(amount,idx+1)%mod;
  93.  
  94.         return dp[amount][idx]=(ret1+ret2)%mod;
  95. }
  96.  
  97. int main()
  98. {
  99.     READ("in.txt");
  100.     int tc,cas=1;
  101.     cin>>tc;
  102.     while(tc--)
  103.     {
  104.         pf("Case %d: ",cas++);
  105.         SD2(con,make);
  106.         repl(i,con)
  107.             SDi(coin[i]);
  108.         mem(vis,false);
  109.         int ans = call(0,1);
  110.             pf("%d\n",ans%mod);
  111.     }
  112.     return 0;
  113. }
create a new version of this paste RAW Paste Data