九度笔记之项目安排 - c++编程基础

n>>p.btime>>p.etime>>p.pf;
p.id = i;
p.order = 0;
pv.push_back(p);
}
std::sort(pv.begin(),pv.end(),lessthan);
for(std::vector::size_type st = 0;st pv.at(st).order = st;
}

manageP(-1,0,pv);
std::cout< }

int _tmain(int argc, _TCHAR* argv[])
{
int n =0;
while(std::cin>>n){
test1499( n);
}

return 0;
}

// test1499.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
#include
#include

struct Project{
int id;
int order;//记录排序后的位置，便于搜寻下一个项目
int btime;
int etime;
int pf;
};
//std::vector userp;
int allpf=0;//盈利
bool lessthan(const Project &a,const Project &b){
return a.btime < b.btime;
}
int getNextP(int curOrder,const std::vector &pv){//得到和项目cur时间不重叠的下一个项目
if(curOrder==-1)
return 0;
std::vector::const_iterator cit = pv.begin() + curOrder +1;
for(;cit!=pv.end();cit++){
if(cit->btime >= pv.at(curOrder).etime){
return cit->order;
}
}
if(cit==pv.end()){
return -1;
}
}
/*
int getAdjacentP(const Project &cur, const std::vector &pv){//得到开始时间在项目cur开始时间之后或重合的下一个项目
if(cur.order == pv.size()-1)
return 0;
else
return cur.order+1;
}
*/
void manageP(int curOrder,int curpf,const std::vector &pv){//已经加入了k-1个项目，k-1为cur项目
//加入
int nextOrder;
nextOrder = getNextP(curOrder,pv);
if(nextOrder==-1){
if(curpf>allpf)
allpf = curpf;
return;
}else{
manageP(nextOrder,curpf+pv.at(nextOrder).pf,pv);
}

if(nextOrder == pv.size()-1){ //nextOrder是最后一个项目
if(curpf+pv.at(nextOrder).pf > allpf){
allpf = curpf+pv.at(nextOrder).pf;
return;
}
}else{
int adjacentOrder = nextOrder+1;
if(pv.at(adjacentOrder).btime >= pv.at(nextOrder).etime){ //adjacentOrder开始时间在nextOrder结束时间之后
//得到的利润肯定没有加上nextOrder的多
return;
}else{
manageP(adjacentOrder,curpf+pv.at(adjacentOrder).pf,pv);
}
}

}
void test1499(int n){
int i = 0;
Project p;
std::vector pv;
while(i++ std::cin>>p.btime>>p.etime>>p.pf;
p.id = i;
p.order = 0;
pv.push_back(p);
}
std::sort(pv.begin(),pv.end(),lessthan);
for(std::vector::size_type st = 0;st pv.at(st).order = st;
}

manageP(-1,0,pv);
std::cout< }

int _tmain(int argc, _TCHAR* argv[])
{
int n =0;
while(std::cin>>n){
test1499( n);
}

return 0;
}
[cpp]

id,order成员变量可以去除，新的代码为

[cpp]
#include "stdafx.h"
#include
#include
#include

struct Project{
//int id;
//int order;
int btime;
int etime;
int pf;
};
int allpf=0;
bool lessthan(const Project &a,const Project &b){
return a.btime < b.btime;
}
int getNextP(std::vector::size_type curOrder,const std::vector &pv){
if(curOrder==-1)
return 0;
//std::vector::const_iterator cit = pv.begin() + curOrder +1;
std::vector::size_type t = curOrder +1;
for(; t if(pv[t].btime >= pv[curOrder].etime){
return static_cast(t);
}
}
if(t==pv.size()){
return -1;
}
}

void manageP(std::vector::size_type curOrder,int curpf,const std::vector &pv){

int nextOrder;
nextOrder = getNextP(curOrder,pv);
if(nextOrder==-1){
if(curpf>allpf)
allpf = curpf;
return;
}else{
manageP(static_cast::size_type>(nextOrder),curpf+pv.at(nextOrder).pf,pv);
}

if(nextOrder == pv.size()-1){
if(curpf+pv.at(n

九度笔记之 项目安排 (二)

九度笔记之项目安排 (二)