Блог пользователя Shuaib

Автор Shuaib, 13 лет назад, По-английски

Can someone please spot a problem with my solution to this UVa problem Is Bigger Smarter.

All the tests I've performed gives me correct result but I keep on getting WA on the judge.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <stack>
 
using namespace std;
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
    if(p1.first.first<p2.first.first)
        return true;
    return false;
}
int main()
{
    int w, iq;
    vector<pair<pair<int, int>, int> > v; // to hold ((weight, iq), index_in_input)
    int i=1;
    while(cin>>w>>iq)
    {
        v.push_back(make_pair(make_pair(w, iq), i));
        i++;
    }
    sort(v.begin(), v.end(), cmp); //sort by weight
    vector<int> dp(v.size(), 1);
    vector<int> s(v.size());
    for(int i=0;i<s.size();i++)
        s[i] = i;
    int max = 1;
    int maxi=0;
    int lmaxi = 0;
    /*
     * In the following loop, find the longest decreasing subsequence on IQ,
     * such that for each successive member, weight is more then the previous
     * one. Also storing index of maximum length found thus far, and the choice
     * made to get till there.
     */
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second)
            {
                dp[i] = dp[j]+1;
                s[i] = j;
                if(dp[i]>max)
                {
                    max = dp[i];
                    maxi = i;
                }
            }
        }
    }
    cout<<max<<endl;
    stack<int> st;
    /*
     * Push choices made to get to the largest subsquence in a stack. And print
     * them in reverse.
     */
    for(int i=0;i<max;i++)
    {
       st.push(v[maxi].second);
       maxi = s[maxi];
    }
    for(int i=0;i<max;i++)
    {
        cout<<st.top()<<endl;
        st.pop();
    }
    return 0;
}
Теги dp, uva
  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
C'mon guys, what is so negative about this post? The down votes has made it disappear from activity list. If you couldn't respond with helpful comments, at least could have refrained from down voting it to sink so someone else could have a look.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Found the issue:
if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second)
becomes:
if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second && dp[i]<=dp[j])