c++ - 美丽的人-动态编程

我正在尝试解决http://acm.sgu.ru/problem.php?contest=0&problem=199上的Beautiful People问题，但在某些测试用例中却得到了错误的答案。

Sample test(s)

Input


4
1 1
1 2
2 1
2 2

Output


2
1 4

基本上我的方法是:

首先针对Beauty []将数组Strength []排序

采用数组D [i]，该数组存储最大lis直到i

最优解= D(i) = { 1 + Max ( D(j) ) }，其中j < i和D[i] = max{ D[j] +1 }和j < i的Strength[j] < Strength[i]和Beauty[j] < Beauty[i]，如果没有这样的j，则D(i) = 1

我的方法中缺少任何内容吗？

我的解决方案:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct {
    long int s;
    long int b;
} c_type;
int compare(const c_type &a,
        const c_type &b) {
    return a.s < b.s;
}

int main( )
{


int n = 0;
cin>>n;
vector<c_type> ct;
ct.resize(n);
//vector<long int> b(n,-1);
//s[0] = 1;
//s[1] = 1;
//s[2] = 2;
//s[3] = 2;
//b[0] = 1;
//b[1] = 2;
//b[2] = 1;
//b[3] = 2;

vector<long int> d(n,1);
vector<long int> p(n,-1);
long int max = -1;
long int bestEnd = -1;
for(int i = 0 ;i<n;i++)
{
    cin>>ct[i].s>>ct[i].b;
}
 sort (ct.begin(), ct.end(), compare);
for(int i  = 1 ; i < n ;i++)
{
    for(int j  = i-1 ; j>=0 ; j--)
    {
        if(((d[j] + 1) > d[i]) and (ct[j].b < ct[i].b) and (ct[j].s < ct[i].s))
        {
            d[i] = d[j]+1;
            p[i] = j;
        }
    }
    if(max < d[i])
    {
        max = d[i];
        bestEnd = i;
    }
}
cout<<max<<endl;
if(bestEnd != -1)
while(bestEnd not_eq -1)
{
    cout<<bestEnd+1<<" ";
    bestEnd = p[bestEnd];
}
return 0;
}

最佳答案

您的解决方案为人员输出了错误的索引。对输入进行排序后，它们的顺序将发生变化。只需将其他索引存储到您的结构中并使用它即可。
但是，您的代码将获得TLE，原因是O(N ^ 2)。您需要O(NlogN)解决方案，这是LIS的经典解决方案。