[HDU1160]FatMouse's Speed
2024-10-01 10:03:56
题目大意:读入一些数(每行读入$w[i],s[i]$为一组数),要求找到一个最长的序列,使得符合$w[m[1]] < w[m[2]] < ... < w[m[n]]$且$s[m[1]] > s[m[2]] > ... > s[m[n]]$,并输出每组数在读入时的顺序(具体见原题目)。
思路:先根据w从小到大排序,再求最长下降子序列,DP时保存路径,最后递归输出路径。
C++ Code:
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int n=1;
struct sz{
int w,s,num;
bool operator <(const sz& rhs)const{
if(w!=rhs.w)return w<rhs.w;
return s>rhs.s;
}
}a[1020];
int d[1020],p[1020];
void dg(int n){
if(n==0)return;
dg(d[n]);
printf("%d\n",a[n].num);
}
int main(){
while(scanf("%d%d",&a[n].w,&a[n].s)!=EOF)a[n].num=n,n++;
n--;
sort(a+1,a+n+1);
memset(d,0,sizeof(d));//d[i]表示i的前一个数
memset(p,0,sizeof(p));//p[i]表示以s[i]结尾的最长下降子序列的长度
for(int i=1;i<=n;i++)p[i]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++)
if(a[i].w>a[j].w&&a[i].s<a[j].s){//a[i].w>a[j].w不能去掉,因为可能出现两个w相等的情况
if(p[i]<p[j]+1){
p[i]=p[j]+1;
d[i]=j;
}
}
}
int t,max=0;
for(int i=1;i<=n;i++)
if(max<p[i]){
t=i;
max=p[i];
}
printf("%d\n",max);
dg(t);
return 0;
}
最新文章
- jQuery验证控件jquery.validate.js使用说明+中文API
- Bootstrap<;基础一>; CSS 概览
- 似乎都设置了utf-8,为什么出现乱码
- 如何杀掉D状态的进程?[zt]【转】
- C# 类的多态、结构、接口、抽象、虚函数总结
- Queue and Message
- Redis系统学习 四、超越数据结构
- 用cas来实现php的单点登陆
- dialog使用方法(同一页面,调用一个js代码,实现多个不同样式的弹窗)
- Linux文件锁定保护命令chattr介绍
- 动态创建 script 实现跨域请求数据
- Frame buffer分析 - fbmem.c【转】
- MySQL中间件之ProxySQL(9):ProxySQL的查询缓存功能
- BZOJ3772 精神污染 主席树 dfs序
- 【MySQL (六) | 详细分析MySQL事务日志redo log】
- immutable.js使用总结
- Android padding 和margin
- 设计模式之迭代器模式(Iterator Pattern)
- 腾讯云Mac图床插件
- 每日一问(如何在List中加入、设置、获取和删除其中的元素?)
热门文章
- 【BZOJ3600】没有人的算术 - 替罪羊树+线段树
- web前端对文件的引用规则
- android onConfigurationChanged的那点事
- swiper.js在隐藏/显示切换时,轮播出现bug的解决办法
- Updates were rejected because the remote contains work that you do(gitee报错解决方案)
- 启动 Appium 自带模拟器
- Spring 让 LOB 数据操作变得简单易行
- 多播 &; multicast
- linux 下password加密程序(能够用于替换shadow文件里的用户password)
- Bootstrap警告