fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int w[105], p[105], dp1[105][505], dp2[105][505], n, C;
  5. string s;
  6.  
  7. void init(){
  8.     for(int i=0; i<105; i++){
  9.         for(int j=0; j<505; j++){
  10.             dp1[i][j] = -1;
  11.             dp2[i][j] = -1;
  12.         }
  13.     }
  14. }
  15.  
  16. int knapsack(int i, int j){
  17.     if(i<0 || j<=0)  return 0;
  18.     if(dp1[i][j]!=-1)    return dp1[i][j];
  19.     int nT = knapsack(i-1, j);
  20.     int T = -1;
  21.     if(w[i]<=j) T = p[i] + knapsack(i-1, j-w[i]);
  22.     return dp1[i][j] = max(nT, T);
  23. }
  24.  
  25. int totalWeight(int i, int j, string x = ""){
  26.     if(i<0 || j<=0)  return 0;
  27.     if(dp2[i][j]!=-1)    return dp2[i][j];
  28.     int nT = knapsack(i-1, j);
  29.     int T = -1;
  30.     if(w[i]<=j) T = p[i] + knapsack(i-1, j-w[i]);
  31.     if(nT > T)  return dp2[i][j] = totalWeight(i-1, j);
  32.     if(T > nT)  return dp2[i][j] = w[i] + totalWeight(i-1, j-w[i]);
  33.     return dp2[i][j] = min(totalWeight(i-1, j), w[i] + totalWeight(i-1, j-w[i]));
  34. }
  35.  
  36.  
  37. void minC(int i, int j, string x=""){
  38.     if(i<0 || j<=0){
  39.         cout<<x<<endl;
  40.         return;
  41.     }
  42.     int nT = totalWeight(i-1, j);
  43.     int T = -1;
  44.     if(w[i]<=j) T = w[i] + totalWeight(i-1, j-w[i]);
  45.     if(nT > T)  minC(i-1, j, x);
  46.     else    minC(i-1, j-w[i], (char)s[i]+x);
  47. }
  48.  
  49. int main(){
  50.     cin>>s;
  51.     cin>>C;
  52.     n = s.size();
  53.     for(int i=0; i<n; i++){
  54.         w[i] = 50 + ((int)s[i])%10;
  55.         p[i] = 5 + ((int)s[i])%5;
  56.     }
  57.     init();
  58.     int v1 = knapsack(n-1, C);
  59.     int v2 = totalWeight(n-1, C);
  60.     minC(n-1, C);
  61.     cout<<"Total weight: "<<v2<<", Total height: "<<v1;
  62.  
  63. }
  64. /*
  65. ihateyou
  66. 330: (321, 41)
  67. 276: (270, 35)
  68. 225: (219, 29)
  69. 212: (207, 27)
  70. */
  71.  
  72.  
  73.  
Success #stdin #stdout 0.01s 5448KB
comments (?)
stdin
copy 
ihateyou
330
stdout
copy 
ihateu
Total weight: 321, Total height: 41
https://ideone.com/E9bJ2L
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!