d,p:array[0..500] of real；
a:array[0..500,0..500] of real；
re:real；
i,j,k,n,pan:integer；
st:string；
begin
read(d1,c,d2,p[0],n)；
d[n+1]:=d1；
for i:=1 to n do
read(d[i],p[i])；
d[0]:=0；
for i:=0 to n do
if c*d2<d[i+1]-d[i] then begin
pan:=-1；break；end；
if pan<>-1 then begin
for i:=0 to n+1 do
for j:=0 to n+1 do
a[i,j]:=100000；
for i:=0 to n do
for j:=i+1 to n+1 do
if ((d[j]-d[i])/d2)>c then break
else a[i,j]:=((d[j]-d[i])/d2)*p[i]；
for j:=2 to n+1 do
for i:=n-1 downto 0 do
for k:=i+1 to j-1 do
if (a[i,k]<>100000)and(a[k,j]<>100000)and(a[i,j]>a[i,k]+a[k,j]) then
a[i,j]:=a[i,k]+a[k,j]；
str(trunc(a[0,n+1]*1000),st)；
n:=length(st)；
if ord(st[n])>ord(’4’) then if st[n-1]<>’9’ then
st[n-1]:=chr(ord(st[n-1])+1)
else begin st[n-1]:=’0’；st[n-2]:=chr(ord(st[n-2])+1)；end；
for i:=1 to n-1 do begin
if i=n-2 then write(’.’)；
write(st[i])；end；
end
else write(’No Solution’)；
end.
状态题目:旅行家的预算
题目编号:347-旅行家的预算 查看该题
状态: Accepted
测评机： Xeost[5]
得分： 100分
提交日期： 2008-10-14 20:21:00
有效耗时： 204毫秒
测试结果1: 通过本测试点|有效耗时63:ms
测试结果2: 通过本测试点|有效耗时47:ms
测试结果3: 通过本测试点|有效耗时47:ms
测试结果4: 通过本测试点|有效耗时47:ms
提交代码： //Greedy+Simulation
#include<fstream>
#include<iomanip>
#include<iostream>
#define maxn 100
using namespace std；
#define fin cin
#define fout cout
//ifstream fin ("travel.in")；
//ofstream fout ("travel.out")；
bool no；
double thebefore,dist,nowp,cost,dp,d1,c,d2,p1；
int i,j,temp,n；
int place[maxn+1]；
double p[maxn+1],d[maxn+1]；
double gas[maxn+1]；
int main (void){
fin>>d1>>c>>d2>>p1>>n；
dp=d2；
p[0]=p1；
d[0]=0.0；
d[n+1]=d1；
no=false；
for (i=1；i<=n；i++){
fin>>d[i]>>p[i]；
if (d[i]-d[i-1]>dp*c)
no=true；
}
if (d[n+1]-d[n]>dp*c)
no=true；
if (no){
fout<<"No Solution"<<endl；
return 0；
}
for (i=0；i<=n；i++)
place[i]=i；
for (i=0；i<=n-1；i++)
for (j=i+1；j<=n；j++)
if (p[place[i]]<p[place[j]]){
temp=place[i]；
place[i]=place[j]；
place[j]=temp；
}
memset(gas,0,sizeof(gas))；
cost=0.0；
nowp=0.0；
for (i=0；i<=n；i++){
gas[i]=c-nowp；
for (j=0；j<=n；j++)
if (place[j]<i&&p[place[j]]>p[i]){
gas[i]+=gas[place[j]]；
gas[place[j]]=0.0；
}
dist=d[i+1]-d[i]；
nowp=c-dist/dp；
thebefore=dist/dp；
for (j=n；j>=0；j--)
if (gas[place[j]]>0){
if (gas[place[j]]<thebefore){
thebefore-=gas[place[j]]；
cost+=gas[place[j]]*p[place[j]]；
gas[place[j]]=0.0；
}
else{
gas[place[j]]-=thebefore；
cost+=thebefore*p[place[j]]；
break；
}
}
}
fout<<fixed<<setprecision(2)<<cost<<endl；
return 0；
}