hdu 1160 上升序列 dp
FatMouse's Speed
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 23350 Accepted Submission(s): 10391
Special Judge
believes that the fatter a mouse is, the faster it runs. To disprove
this, you want to take the data on a collection of mice and put as large
a subset of this data as possible into a sequence so that the weights
are increasing, but the speeds are decreasing.
The
data for a particular mouse will consist of a pair of integers: the
first representing its size in grams and the second representing its
speed in centimeters per second. Both integers are between 1 and 10000.
The data in each test case will contain information for at most 1000
mice.
Two mice may have the same weight, the same speed, or even the same weight and speed.
program should output a sequence of lines of data; the first line
should contain a number n; the remaining n lines should each contain a
single positive integer (each one representing a mouse). If these n
integers are m[1], m[2],..., m[n] then it must be the case that
W[m[1]] < W[m[2]] < ... < W[m[n]]
and
S[m[1]] > S[m[2]] > ... > S[m[n]]
In order for the answer to be correct, n should be as large as possible.
All
inequalities are strict: weights must be strictly increasing, and
speeds must be strictly decreasing. There may be many correct outputs
for a given input, your program only needs to find one.
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int w;
int v;
int num;
}p[];
bool cmp(node a,node b)//重量递增,速度递减
{
if(a.w<b.w)
return a.w<b.w;
else if(a.w==b.w&&a.v>b.v)
return a.v>b.v;
else
return ;
}
int dp[],pre[],ans[];
//dp[i]表示以第i个数据结尾的符合要求的子序列长度
//pre[i]记录i对应的上一个数据的下标(滚动数组,这里的上一个是指符合要求的数据,所以,pre[i]!=dp[i-1])
//ans[i]存放符合要求的数据的下标(排序之后的下标,输出的时候要对应回去)
int main()
{
int i=;
while(~scanf("%d%d",&p[i].w,&p[i].v))
{
p[i].num=i;
dp[i]=;
pre[i]=-;
i++;
}
int n=i,len=,x;//len最长序列长度,x最长序列长度的下标
sort(p,p+n,cmp); for(int i=;i<n;i++)
{
for(int j=;j<i;j++)
{
if(p[i].w>p[j].w&&p[i].v<p[j].v&&dp[j]+>dp[i])
{
dp[i]=dp[j]+;
pre[i]=j;
if(dp[i]>len)
{
len=dp[i];
x=i;
}
}
}
}
int k=;
while(x!=-)
{
ans[k++]=x;
x=pre[x];
}
printf("%d\n",k);//输出最长序列长度
for(int i=k-;i>=;i--)
{
printf("%d\n",p[ans[i]].num+);
}
return ;
}
最新文章
- LBaaS 实现机制 - 每天5分钟玩转 OpenStack(125)
- React 学习笔记(一)
- <;构建之法>;之一至二章
- 使用VS2010开发Qt程序的一点经验(转载)
- IOS 实现自定义的导航栏背景以及自定义颜色的状态栏(支持7.0以及低版本)
- WSGI规格说明书
- Android应用自动更新功能的实现!!!
- 存储过程中调用EXECUTE IMMEDIATE的“权限不足”问题
- mysql 自带的压力测试
- Java常用类--数字常用类
- Sleep和wait
- 线程间的通信_多生产者多消费者问题_JDK1.5新特性_Lock
- mybatis源码解析2---SqlSessionFactoryBuilder、SqlSessionFactory解析
- 安装express并创建工程
- k近邻算法-java实现
- Oracle数据库system用户忘记了密码怎么办
- 模型融合策略voting、averaging、stacking
- 过滤器 ;spring拦截器 切片 小结
- strcpy函数;memcpy函数;memmove函数
- mkdoc安装与使用说明
热门文章
- The problem: somthing wrong when my computer excute the command ";git clone XXXX";
- ZCGL大数据平台日常运维问题与解决方法
- python 开启http服务并下载文件
- MariaDB——数据库集群
- 「JSOI2007」建筑抢修
- 修改了ssh默认端口对git的影响
- 【C#】关于左移/右移运算符的使用
- Springboot配置文件内容加密
- ffmpeg 学习: 004-参考文档进行的开发
- C2 - Skyscrapers (hard version)