HDU-1160-FatMouse's Speed(DP, 最长递增子序列)
2024-09-04 03:16:40
链接:
https://vjudge.net/problem/HDU-1160
题意:
FatMouse 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.
思路:
对s排序, 然后最长递增子序列,nlogn总有bug还是n2好用
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <sstream>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const LL MOD = 20090717;
const int MAXN = 1e3+10;
struct Node
{
int w, s;
int id;
bool operator < (const Node& that) const
{
return this->s > that.s;
}
}node[MAXN];
int Dp[MAXN], Pre[MAXN];
int n;
void Print(int p)
{
if (p == -1)
return;
Print(Pre[p]);
printf("%d\n", node[p].id);
}
int main()
{
int l, r;
while (~scanf("%d%d", &l, &r))
{
node[++n].w = l;
node[n].s = r;
node[n].id = n;
}
sort(node+1, node+1+n);
memset(Pre, -1, sizeof(Pre));
memset(Dp, 0, sizeof(Dp));
for (int i = 1;i <= n;i++)
{
Dp[i] = 1;
for (int j = 1;j < i;j++)
{
if (node[i].w > node[j].w && node[i].s < node[j].s)
{
if (Dp[j]+1 > Dp[i])
{
Dp[i] = Dp[j]+1;
Pre[i] = j;
}
}
}
}
int maxval = 1, maxpos = 1;
for (int i = 1;i <= n;i++)
{
if (maxval < Dp[i])
{
maxval = Dp[i];
maxpos = i;
}
}
printf("%d\n", maxval);
Print(maxpos);
return 0;
}
最新文章
- sublime 函数跳转插件 — ctags 安装和使用
- c8051f320学习,单片机不外乎时钟、IO、串口、USB等外设用法
- 关于centos的yum代理设置
- 【经典】C++&;RPG对战游戏
- Linux的常用基本命令
- Asp.net MVC4 网站发布
- Hibernate注解:一对一主键关联
- Spring JTA应用JOTM &; Atomikos II JOTM
- sgu 185 最短路建网络流
- 数据库事务的ACID和BASE
- [BZOJ 2004] [Hnoi2010] Bus 公交线路 【状压DP + 矩阵乘法】
- 数据结构学习:KMP模式匹配算法
- 8.C++-类的关键字
- Swift中 删除Array的元素对象
- truecrype加密卷的使用
- poj1990两个树状数组
- Javascript中的垃圾回收机制
- Linux基础命令---sum,cksum
- Unity 3D游戏-见缝插针源码
- JavaScript实现本地图片上传预览功能(兼容IE、chrome、FF)