Guest User

Dp question

a guest
Dec 10th, 2018
45
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4. struct state{
  5. set<ll> last; //height of last histogram picked
  6. ll max_val; //value of best possible answer
  7. map <ll,ll> max_val_count; //count of best possible answer
  8. state(){
  9. max_val=0;
  10. }
  11. };
  12. ll heights[100],N,lim,temp;
  13. int main()
  14. {
  15. ios_base::sync_with_stdio(false);
  16. cin.tie(NULL);
  17. cout.tie(NULL);
  18.  
  19. cin>>N;
  20. lim=pow(2,N)-1;
  21. for(int i=0;i<N;i++) cin>>heights[i];
  22.  
  23. struct state dp[33000]; //you only need up to 0-32,768
  24. dp[0].max_val=0;
  25. dp[0].max_val_count[0]=1;
  26. dp[0].last.insert(0);
  27. for(int i=1;i<=lim;i++){
  28. for(int j=0;j<N;j++){
  29. if(i&(1<<j)){
  30. // if jth bit is set , unset it and find the answer for the remaining bits
  31. set <ll>::iterator it;
  32. for( it=dp[i&~(1<<j)].last.begin();it!=dp[i&~(1<<j)].last.end();it++){
  33. temp=dp[i&~(1<<j)].max_val - *it + abs(*it-heights[j]) + heights[j] +2;
  34. if(temp>dp[i].max_val){
  35. dp[i].max_val=temp;
  36. dp[i].max_val_count.clear(); dp[i].max_val_count[heights[j]]=(dp[i&~(1<<j)].max_val_count[*it]);
  37. dp[i].last.clear(); dp[i].last.insert(heights[j]);
  38. }
  39. else if(temp==dp[i].max_val){
  40. dp[i].max_val_count[heights[j]]+=(dp[i&~(1<<j)].max_val_count[*it]);
  41. dp[i].last.insert(heights[j]);
  42. }
  43. }
  44. }
  45. }
  46. cout<<i<<"::"<<dp[i].max_val<<" ";
  47. for(auto it=dp[i].last.begin();it!=dp[i].last.end();it++) cout<<*it<<":"<<dp[i].max_val_count[*it]<<" ";
  48. cout<<endl;
  49. }
  50. ll ans=0;
  51. for(auto it=dp[lim].last.begin();it!=dp[lim].last.end();it++) ans+=dp[lim].max_val_count[*it];
  52. cout<<dp[lim].max_val<<" "<<ans<<endl;
  53. return 0;
  54. }
RAW Paste Data