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;
}