fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fi(i, a, b) for(int i = a; i < b ; ++i)
  3. #define fd(i, a, b) for(int i = a; i > b ; --i)
  4. #define all(c) c.begin(), c.end()
  5. #define llu long long
  6.  
  7. using namespace::std;
  8. vector<int> cost, r, s, dp;/**cost stores the cost of various lengths of the rod cost[0] = 0**/
  9.                                             /** s stores the index(or cut) for each smaller rod (smaller sub prob) such that revenue of that sub rod is maximized**/
  10. int n;                              /**the length of the rod **/
  11. int f(int i)
  12. {
  13.     if(i <=0 || i > n)              /**rod of length less than zero generates zero revenue**/
  14.         return 0;
  15.     if(dp[i] == -1)                 /**if result for this sub rod has'nt been calculated yet**/
  16.             {
  17.                 for(int j = 1; j <=  i ; ++j)               /**loop thru all possible sub rods to find the one which generates max revenue**/
  18.                 if(dp[i] < cost[j]+f(i-j))              /** cost[j]+f(i-j) means cost of a sub rod + max revenue of the rest of the len**/
  19.                 {                                                           /**the recursion style is the basis 4 top down DP**/
  20.                     dp[i] = cost [j] + dp[i-j];
  21.                     s[i] = j;                                           /**update the sub rod each time we find a cut with better revenue**/
  22.                 }                                                           /**thus at the end of the loop dp[i] stores the max revenue for a rod of length i (it has analysed all possible sub rods)**/
  23.             }
  24.      return dp[i];                                      /**dp[i] is returned to f(i), hence f(x) returns returns max rev for rod of length x **/
  25. }
  26. int main()
  27. {
  28.     int T,i = 0;
  29.    // freopen("in.txt", "r", stdin);
  30.      // freopen("out2.txt", "w", stdout);
  31.     cout<<"\nenter the no of test cases";
  32.  
  33.         cin>>T;
  34.         while(T--)
  35.         {
  36.             cout<<"\nenter the length of the rod "<<endl;
  37.             cin>>n;
  38.  
  39.             dp = vector<int> (n+1, -1);
  40.             cost = vector<int> (n+1, 0);
  41.             s = vector<int> (n+1, 0);
  42.             i = 0;
  43.             while(i<=n)
  44.                 {
  45.                     cin>>cost[i];
  46.                     cout<<"\nenter the cost of size "<<i++<<"\t:"<<endl;
  47.                     cout<<cost[i-1];
  48.                 }
  49.                 dp[0] = 0;
  50.                 dp[1] = cost[1];
  51.             cout<<"\nmax revenue is :\t"<<f(n)<<endl;
  52.             cout<<"\narray s is :\n";
  53.             for(auto it : s)
  54.                 cout<<it<<' ';
  55.             cout<<"\narray dp is :"<<endl;
  56.             for(auto it : dp)
  57.                 cout<<it<<' ';
  58.             cout<<endl;
  59.         }
  60.         return 0;
  61. }
  62.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
2
9
0 1 5 7 9 10 16 18 20 22
10
0 1 5 8 9 10 17 17 20 24 30
stdout
copy 
enter the no of test cases
enter the length of the rod 

enter the cost of size 0	:
0
enter the cost of size 1	:
1
enter the cost of size 2	:
5
enter the cost of size 3	:
7
enter the cost of size 4	:
9
enter the cost of size 5	:
10
enter the cost of size 6	:
16
enter the cost of size 7	:
18
enter the cost of size 8	:
20
enter the cost of size 9	:
22
max revenue is :	23

array s is :
0 0 2 3 2 2 6 7 2 2 
array dp is :
0 1 5 7 10 12 16 18 21 23 

enter the length of the rod 

enter the cost of size 0	:
0
enter the cost of size 1	:
1
enter the cost of size 2	:
5
enter the cost of size 3	:
8
enter the cost of size 4	:
9
enter the cost of size 5	:
10
enter the cost of size 6	:
17
enter the cost of size 7	:
17
enter the cost of size 8	:
20
enter the cost of size 9	:
24
enter the cost of size 10	:
30
max revenue is :	30

array s is :
0 0 2 3 2 2 6 1 2 3 10 
array dp is :
0 1 5 8 10 13 17 18 22 25 30
https://ideone.com/uqF87G
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!