Advertisement
Saleh127

UVA 10131 / DP

Nov 23rd, 2021
591
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-08-18.37.18
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. ll dp[20005];
  12. ll seq[20005];
  13. vector<ll>ans;
  14.  
  15. struct bal
  16. {
  17.     ll id;
  18.     ll w;
  19.     ll s;
  20.  
  21.     bool operator<(const bal & x)const
  22.     {
  23.         if(w!=x.w) return w<x.w;
  24.         return s>=x.s;
  25.     }
  26.  
  27.  
  28. } node[20005];
  29.  
  30. void output(ll k)
  31. {
  32.      if(seq[k]!=k) output(seq[k]);
  33.  
  34.      cout<<node[k].id<<nl;
  35. }
  36.  
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.  
  43.  
  44.     ll n=0,m,i,j,k=0,l=0;
  45.  
  46.     while(scanf("%lld %lld",&i,&j)!=EOF)
  47.     {
  48.         n++;
  49.         node[n].w=i;
  50.         node[n].s=j;
  51.         node[n].id=n;
  52.     }
  53.  
  54.     sort(node+1,node+n+1);
  55.  
  56.     for(i=1; i<=n; i++)
  57.     {
  58.         dp[i]=1;
  59.         seq[i]=i;
  60.  
  61.         for(j=1; j<i; j++)
  62.         {
  63.             if(node[i].w>node[j].w && node[i].s<node[j].s)
  64.             {
  65.                 if(dp[j]+1>dp[i])
  66.                 {
  67.                     dp[i]=dp[j]+1;
  68.                     seq[i]=j;
  69.                 }
  70.             }
  71.         }
  72.         if(dp[i]>l)
  73.         {
  74.             l=dp[i];
  75.             k=i;
  76.         }
  77.     }
  78.  
  79.  
  80.     cout<<l<<nl;
  81.  
  82.     output(k);
  83.  
  84.  
  85.     get_lost_idiot;
  86. }
  87.  
  88.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement