题目
源地址:
http://codeforces.com/problemset/problem/4/D
理解
题目好像是俄罗斯套娃的二维版,就是求一个二维的最长上升子序列问题。 只要按照其中一个变量排序,然后求第二个变量的最长上升子序列即可。
代码
#define MAXN 5000+10
struct node
{
int no;
int w;
int h;
int prev;
int l;
node(int no, int w, int h, int prev, int l)
{
this->no = no;
this->w = w;
this->h = h;
this->prev = prev;
this->l = l;
}
bool operator < (const node& e) const
{
return (w < e.w);
}
};
int n, w, h;
int tmpw, tmph;
int cmp(node e1, node e2)
{
if (e1.w < e2.w && e1.h < e2.h) return 1;
return -1;
}
int main(int argc, char const *argv[])
{
vector<node> envs;
scanf("%d %d %d", &n, &w, &h);
for (int i = 0; i < n; i++)
{
scanf("%d %d", &tmpw, &tmph);
if (tmpw <= w || tmph <= h) continue;
envs.push_back(node(i+1, tmpw, tmph, -1, 1));
}
sort(envs.begin(), envs.end());
for (int i = 0; i < envs.size(); i++)
{
for (int j = 0; j < i; j++)
{
if (cmp(envs[j], envs[i]) <= 0) continue;
if (envs[i].l >= envs[j].l + 1) continue;
envs[i].l = envs[j].l + 1;
envs[i].prev = j;
}
}
int maxl = 0, pos = -1;
for (int i = 0; i < envs.size(); i++)
{
if (envs[i].l <= maxl) continue;
maxl = envs[i].l;
pos = i;
}
if (maxl == 0)
{
printf("0\n");
}
else
{
stack<int> s;
while (pos != -1)
{
s.push(envs[pos].no);
pos = envs[pos].prev;
}
printf("%d\n%d", s.size(), s.top());
s.pop();
while (!s.empty())
{
printf(" %d", s.top());
s.pop();
}
printf("\n");
}
return 0;
}
更新日志
- 2014年11月7日 已AC。