我正在试图解决http://acm.sgu.ru/problem.php?contest=0&problem=199上的美丽人问题，但在一些测试用例中得到了错误的答案。
一座城市中最负盛名的运动俱乐部有N个成员。每个成员都强壮而美丽。更准确地说，该俱乐部的第i位成员（成员按他们加入俱乐部的时间编号）具有力量Si和美丽Bi。由于这是一个非常负有声望的俱乐部，其成员非常富有，因此是非凡的人，他们经常极度憎恨彼此。严格来说，如果Si ≤ Sj并且Bi ≥ Bj或者Si ≥ Sj并且Bi ≤ Bj（如果Mr X的两个属性都大于Mr Y的相应属性，则他甚至不会注意到他，另一方面，如果他的两个属性都较小，则他非常尊重Mr Y），则俱乐部的第i位成员Mr X憎恨俱乐部的第j位成员Mr Y。为了庆祝新的2003年，俱乐部的管理层计划组织一次聚会。但是，他们担心如果两个互相憎恨的人同时参加聚会，在喝上一两杯之后，他们会开始打架。因此，不应邀请任何互相憎恨的两个人。另一方面，为了保持俱乐部的声望，管理层希望邀请尽可能多的人。
作为唯一一个不害怕接触计算机的管理人员，您需要编写一个程序，找出应该邀请哪些人参加聚会。
输入 输入文件的第一行包含整数N-俱乐部成员的数量。（2 ≤ N ≤ 100,000）。接下来的N行分别包含两个数字-Si和Bi（1 ≤ Si，Bi ≤ 10 ^ 9）。
输出 在输出文件的第一行上打印可以邀请参加聚会的最大人数。在第二行中输出N个整数-要邀请的成员编号，顺序任意。如果有几种解决方案，则输出任何一个。
Sample test(s)
Input
4
1 1
1 2
2 1
2 2
Output
2
1 4
基本上我的方法是：
- 首先根据Beauty[]对Strength[]数组进行排序
- 创建一个数组D[i]，用于存储到i为止的最大lis
- 最优解 =
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;
}