fork download 
  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;
  9.  
  10. int f(int n)
  11. {
  12.     for(int i = 2; i <= n ; ++i)
  13.             for(int j = 1; j <=  i ; ++j)
  14.                 if(dp[i] < cost[j]+dp[i-j])
  15.                 {
  16.                     dp[i] = cost [j] + dp[i-j];
  17.                     s[i] = j;
  18.                 }
  19.      return (dp[n]);
  20. }
  21. int main()
  22. {
  23.     int n, T,i = 0;
  24. //    freopen("in.txt", "r", stdin);
  25. //      freopen("out.txt", "w", stdout);
  26.     cout<<"\nenter the no of test cases";
  27.  
  28.         cin>>T;
  29.         while(T--)
  30.         {
  31.             cout<<"\nenter the length of the rod "<<endl;
  32.             cin>>n;
  33.  
  34.             dp = vector<int> (n+1, -1);
  35.             cost = vector<int> (n+1, 0);
  36.             s = vector<int> (n+1, 0);
  37.             i = 0;
  38.             while(i<=n)
  39.                 {
  40.                     cin>>cost[i];
  41.                     cout<<"\nenter the cost of size "<<i++<<"\t:"<<endl;
  42.                     cout<<cost[i-1];
  43.                 }
  44.                 dp[0] = 0;
  45.                 dp[1] = cost[1];
  46.             cout<<"\nmax revenue is :\t"<<f(n)<<endl;
  47.             cout<<"\narray s is :\n";
  48.             for(auto it : s)
  49.                 cout<<it<<' ';
  50.             cout<<"\narray dp is :"<<endl;
  51.             for(auto it : dp)
  52.                 cout<<it<<' ';
  53.             cout<<endl;
  54.         }
  55.         return 0;
  56. }
  57.  
Success #stdin #stdout 0s 3436KB
comments ()
stdin 
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 
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/2LfUUz
language:
C++14 (gcc 8.3)
created:
10 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!