ccbeginner

UVa Q10131

Feb 8th, 2020
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10131
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct ele{
  6.     int W, Q, idx;
  7. }arr[1001];
  8. bool cmp(ele a, ele b){
  9.     if(a.W == b.W)return a.Q < b.Q;
  10.     else return a.W < b.W;
  11. }
  12. int dp[1001], track[1001];
  13.  
  14. int32_t main(){
  15.     int n = 1;
  16.     while(cin >> arr[n].W >> arr[n].Q){
  17.         arr[n].idx = n;
  18.         ++n;
  19.     }
  20.     sort(arr+1, arr+n, cmp);
  21.     --n;
  22.     for(int i = 1; i <= n; ++i){
  23.         dp[i] = 1;
  24.         for(int j = 1; j < i; ++j){
  25.             if(arr[i].W > arr[j].W && arr[i].Q < arr[j].Q && dp[i] < dp[j]+1){
  26.                 dp[i] = dp[j]+1;
  27.                 track[i] = j;
  28.             }
  29.         }
  30.     }
  31.     //for(int i = 1; i <=n; ++i)cout << dp[i] << ' ';
  32.     //cout << endl;
  33.     int x = 1;
  34.     for(int i = 2; i <= n; ++i){
  35.         if(dp[i] > dp[x])x = i;
  36.     }
  37.     cout << dp[x] << '\n';
  38.     vector<int> ans;
  39.     while(x){
  40.         ans.emplace_back(arr[x].idx);
  41.         x = track[x];
  42.     }
  43.     for(int i = ans.size()-1; i >= 0; --i)cout << ans[i] << '\n';
  44.     return 0;
  45. }
RAW Paste Data