三、动态规划（1）-Help|三、动态规划（1）-Help Jimmy(POJ1661)
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
#include "stdafx.h"
#include
#include
#include
using namespace std;
#define MAX_N 1000
#define INFINITE 1000000int t, n, x, y, maxHeight;
//组数，平台数，坐标x,y和最大下落高度
structPlatform
{
int Lx, Rx, h;
bool operator<(const Platform& p2)const{//从高到第排序
return h>p2.h;
}};
Platform platform[MAX_N+10];
int leftMinTime[MAX_N + 10];
//个板子从左走最短的时间
int rightMinTime[MAX_N +10];
// 各个板子从右边走最短的时间int main(){
cout << "输入组数：";
cin >> t;
cout << endl;
while (t--){
cout << "输入平台数n，坐标x,y, 最大下落高度：h:" << endl;
cin >> n >> x >> y >> maxHeight;
platform[0].Lx = x;
platform[0].Rx = x;
platform[0].h = y;
//初始位置for (int j = 1;
j <= n;
++j)
cin >> platform[j].Lx >> platform[j].Rx >> platform[j].h;
//重新排序
sort(platform,platform+n+1);
cout << "---------排序队列--------------" << endl;
for (int i = 0;
i <= n;
++i){
cout <= 0;
--i){
int j;
//寻找i的左端下面的板子
for (j = i + 1;
j <= n;
++j){
if (platform[i].Lx <=platform[j].Rx&&platform[i].Lx >= platform[j].Lx)
break;
}
if (j > n){//说明i的左下端不存在板子,下面是地板
if (platform[i].h > maxHeight)
leftMinTime[i] = INFINITE;
else
{
leftMinTime[i] = platform[i].h;
}
}
else
{
int h = platform[i].h - platform[j].h;
if (h > maxHeight)
leftMinTime[i] = INFINITE;
else
leftMinTime[i] = h +
min(leftMinTime[j] + platform[i].Lx - platform[j].Lx,
rightMinTime[j] + platform[j].Rx - platform[i].Lx);
}//寻找i的右端的下面的板子
for (j = i + 1;
j <= n;
++j){
if (platform[i].Rx <= platform[j].Rx&&platform[i].Rx >= platform[j].Lx)
break;
}
if (j > n){// 没找到下方板子
if (platform[i].h > maxHeight){
rightMinTime[i]= INFINITE;
}
else
{
rightMinTime[i] = platform[i].h;
}
}
else{
int h = platform[i].h - platform[j].h;
if (h > maxHeight)
rightMinTime[i] = INFINITE;
else
rightMinTime[i] = h +
min(rightMinTime[j] + platform[j].Rx - platform[i].Rx,
leftMinTime[j] + platform[i].Rx - platform[j].Lx);
}
}cout << "最小时间为：" << min(leftMinTime[0], rightMinTime[0]) << endl;
}
return 0;
}
推荐阅读
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 2018-02-06第三天|2018-02-06第三天 不能再了，反思到位就差改变
- 第三节|第三节 快乐和幸福（12）
- android第三方框架（五）ButterKnife
- 一个人的碎碎念
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- 遇到一哭二闹三打滚的孩子，怎么办┃山伯教育
- Shell-Bash变量与运算符
- 三十年后的广场舞大爷