ACdream 1216 (ASC训练1) Beautiful People(DP)
2024-08-30 00:55:27
题目地址:http://acdream.info/problem?
pid=1216
这题一開始用的是线段树。后来发现查询的时候还须要DP处理。挺麻烦。。也就不了了之了。。后来想到,这题事实上就是一个二维的最长上升子序列。
。
要先排序,先按左边的数为第一keyword进行升序排序。再按右边的数为第二keyword进行降序排序。这种话,第一keyword同样的的肯定不在一个同一个上升子序列中。然后仅仅对第二keyword进行复杂度为O(n*logn)的DP,找出最长上升序列,然后处理前驱,并输出就可以。
代码例如以下:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm> using namespace std;
#define LL long long
struct node
{
int x, y, num;
}fei[110000];
int cmp(node x, node y)
{
if(x.x==y.x)
return x.y>y.y;
return x.x<y.x;
}
int a[110000], d[110000], pre[110000], len, b[110000];
int bin_seach(int x)
{
int low=0, high=len, mid, ans;
while(low<=high)
{
mid=low+high>>1;
if(a[mid]>=x)
{
high=mid-1;
ans=mid;
}
else
{
low=mid+1;
}
}
return ans;
}
int main()
{
int n, i, j, pos, cnt;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d%d",&fei[i].x,&fei[i].y);
fei[i].num=i+1;
}
sort(fei,fei+n,cmp);
len=1;
a[1]=fei[0].y;
d[0]=-1;
d[1]=0;
memset(pre,-1,sizeof(pre));
for(i=1;i<n;i++)
{
if(fei[i].y>a[len])
{
a[++len]=fei[i].y;
pre[i]=d[len-1];
d[len]=i;
}
else
{
pos=bin_seach(fei[i].y);
a[pos]=fei[i].y;
pre[i]=d[pos-1];
d[pos]=i;
}
}
printf("%d\n",len);
cnt=0;
/*for(i=0;i<n;i++)
{
printf("%d ",fei[i].num);
}
puts("");*/
for(i=d[len];i!=-1;i=pre[i])
{
b[cnt++]=fei[i].num;
//printf("%d\n",i);
}
for(i=0;i<cnt-1;i++)
printf("%d ",b[i]);
printf("%d\n",b[cnt-1]);
}
return 0;
}
最新文章
- Android开发学习——android体系结构
- python test
- android.util.TypedValue.applyDimension
- iOS开发UI篇—简单介绍静态单元格的使用
- 实现手机扫描二维码页面登录,类似web微信-第四篇,服务器端
- Ejb: remote调用
- [SSH服务]——一些安全性配置和补充实验
- mvp(1)简介及它与mvc区别
- xcode6 自定义UITabbarController
- careercup-排序和查找 11.3
- WCF - 实例与会话
- 乐视(LeTV)占用8080端口
- 收集Typecho 0.9还能用的插件
- springboot + mybatis +pageHelper分页排序
- busybox(二)编译
- 【python 3】 函数 初识
- B. Divisiblity of Differences
- nginx 负载均衡集群解决方案 healthcheck_nginx_upstreams模块测试 (二)
- F#周报2018年第48期
- JS控制文本框只能输入数字 \保留小数点后两位