动态规划(DP),类似LIS,FatMouse's Speed
2024-10-15 03:36:24
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1108
解题报告:
1、首先按照weight从小到大排列,weight相同的按照speed从大到小排列;
2、Count[i]表示到第i个老鼠时,所求的最长“速度递减”子序列的长度;
3、path[i]=j是题目的关键,记录在Count[i]=Count[j]时,即最长“速度递减”子序列最后一个老鼠的前一只老鼠的位置
4、递归输出id
void output(int path[],pos)
{
if(pos==) return ;
output(path,path[pos]);
printf("%d\n",mice[pos].id);
}
Sources Code:
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f using namespace std; int n;///n只老鼠
int Count[]= {}; ///count[i]表示构造到第i个老鼠时,序列的最大长度
int path[]= {}; ///path[i]表示构造到第i个老鼠时的前一个老鼠(前驱) struct mouse
{
int weight;
int speed;
int id;
} mice[]; int cmp(const void *a,const void *b)
{
struct mouse *p1=(mouse *)a;
struct mouse *p2=(mouse *)b;
if(p1->weight==p2->weight)
{
if(p1->speed>p2->speed)
return p2->speed-p1->speed;
else return p1->speed-p2->speed;
}
else return p1->weight-p2->weight;
} void output(int path[],int pos)
{
if(pos==) return ;
output(path,path[pos]);
printf("%d\n",mice[pos].id);
} int main()
{
n=;
int i=,j=;
while(scanf("%d%d",&mice[++i].weight,&mice[++j].speed)!=EOF)
{
n++;
mice[n].id=n;
}
qsort(mice+,n,sizeof(mice[]),cmp);
Count[]=;
for(int i=; i<=n; i++)
{
for(int j=; j<i; j++)
{
if(mice[i].weight>mice[j].weight&&mice[i].speed<mice[j].speed)
{
if(Count[i]<Count[j])
{
Count[i]=Count[j];
path[i]=j;
}
}
}
Count[i]++;
}
int _max=;
int pos;
for(int i=; i<=n; i++)
{
if(Count[i]>_max)
{
_max=Count[i];
pos=i;
}
}
printf("%d\n",_max);
output(path,pos);
}
最新文章
- Euler猜想
- ionic 发送请求返回一直都是404
- cf.301.D. Bad Luck Island(dp + probabilities)
- 获取shell脚本自身所在目录的Shell脚本分享
- C# HttpHelper 采集
- 判断字符串中是否有SQL攻击代码
- JS初学之-for套for遍历二维数组
- AngularJs学习笔记-慕课网AngularJS实战
- ios Swift 特性
- kernel_task占用大量CPU
- 对 Azure Backup 的常见配置问题进行故障排除
- 打造你的办公环境-email篇
- 如何创建并运行java线程
- 基于Ado.Net的日志组件
- javaIO流实现文件拷贝
- 可迭代对象 TO 迭代器
- (a ==1 &;&; a== 2 &;&; a==3) 有可能是 true 吗?
- 解决编译错误:cc: Internal error: Killed (program cc1)
- python--Numpy简单实用实例
- Phpcms v9专题分类增加模板设置的方法