saketkumarsingh's blog

USACO dp problem:
By saketkumarsingh, 12 months ago, In English

I was trying to solve this question Problem using the concept that answer would be the longest non increasing sequence but it fails on some test cases idk why? Please help me sort it out. Here is my Soln: ~~~~~

#include <bits/stdc++.h>
using namespace std;

int find_lis(vector<int> a) {
    vector<int> dp;
    for (int i : a) {
        int pos = upper_bound(dp.begin(), dp.end(), i)- ``dp.begin();
        if (pos == dp.size()) {
            // we can have a new, longer increasing subsequence!
            dp.push_back(i);
        } else {
            // oh ok, at least we can make the ending element smaller
            dp[pos] = i;
        }
    }
    return dp.size();
}
int main(){
    ifstream fin("cowjog.in");
    ofstream fout("cowjog.out");
    int  n,t;fin>>n>>t;
    vector<vector<int>> v(n, vector<int>(2));
    for(int i=0;i<n;i++) { int x,y;fin>>x>>y; v[i][0]=x, v[i][1]=y; }

    sort(v.begin(), v.end());
    
    vector<int> vec(n);
    for(int i=0;i<n;i++){
        vec[i]=(v[i][0]+t*v[i][1]);
    }
    reverse(vec.begin(), vec.end());
    fout<<find_lis(vec)<<endl;
}

~~~~~

Tags dp, lis
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

i think it should be int pos = lower_bound(dp.begin(), dp.end(), i)- ``dp.begin();

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It isn't, you should have tried it :)

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

LIS isn't the way to go. Here is the answer if you're stuck.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My bad, LIS actually works

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      (Longest Decreasing Sequence over v[i][0]+t*v[i][1])

      → Reply