这道题也没写 pg[i],rune[i]的范围..我想总不能白给吧,不要最大值就无限了.可忽略了一点.那就是 pg了和rune有一个可以为0 只花费其中的一个...唉..失败..
结果只有样例一组数据没有0...其它9组数据全败了...
血的教训啊~~~!!!
大家把自己的DP 过程贴上来,我学习一下
var
f:array[0..150,0..150] of real；
n,p,r,i,j,pp,rr,t,tt:integer；
pg,rune,suit,dps:array[1..150] of integer；
a,b:integer；
c,q:real；
begin
readln(n,p,r)；
for i:=0 to p do
for j:=0 to r do
f[i,j]:=1；
for i:=1 to n do readln(pg[i],rune[i],suit[i],dps[i])；
for i:=1 to n do
for pp:=p downto 1 do
for rr:=r downto 1 do
begin
if pg[i]<>0 then t:=pp div pg[i] else t:=maxint；
if rune[i]<>0 then tt:=rr div rune[i] else tt:=maxint；
if tt<t then t:=tt；
if (suit[i]<>0) and (suit[i]<t) then t:=suit[i]；
a:=0；b:=0；c:=1；
for j:=1 to t do
begin
inc(a,pg[i])；
inc(b,rune[i])；
c:=c*dps[i]/100；
q:=f[pp-a,rr-b]*c；
if q>f[pp,rr] then f[pp,rr]:=q；
end；
end；
writeln(f[p,r]*100:0:4)；
end.
var f:array[0..100,0..100]of real；
cp,cr:array[1..150]of longint；
num:array[1..150]of integer；
dps:array[1..150]of integer；
n,i,j,j1,j2,r,p,s:longint；
begin
readln(n,p,r)；
for i:=0 to 100 do
for j:=0 to 100 do
f[i,j]:=1；
for i:=1 to n do
readln(cp[i],cr[i],num[i],dps[i])；
for i:=1 to n do
begin
if num[i]=0 then
begin
for j1:=cr[i] to r do
for j2:=cp[i] to p do
if f[j1,j2]<f[j1-cr[i],j2-cp[i]]*dps[i]/100 then
f[j1,j2]:=f[j1-cr[i],j2-cp[i]]*dps[i]/100；
end
else
for j:=1 to num[i] do
for j1:=r downto cr[i] do
for j2:=p downto cp[i] do
if f[j1,j2]<f[j1-cr[i],j2-cp[i]]*dps[i]/100 then
f[j1,j2]:=f[j1-cr[i],j2-cp[i]]*dps[i]/100；
end；
writeln(f[r,p]*100:0:4)；
end.
#include<stdio.h>
int n,p,r,pg[151],rune[151],s[151]；
double dps[151]；
double mi(double j,int i)
{
int k；
double t=1.0；
for(k=1；k<=i；k++)
t*=j；
return t；
}
double dp()
{
double m[101][101],dps1；
int i,j,k,t,num,pg1,rune1；
for(i=0；i<=p；i++)
for(j=0；j<=r；j++)
m[i][j]=1.0；
for(i=k；k<=n；k++)
{
if(s[k]==0)
{
for(i=1；i<=p；i++)
for(j=1；j<=r；j++)
{
if(i<pg[k] || j<rune[k])
continue；
if(m[i-pg[k]][j-rune[k]]*dps[k]>m[i][j])
m[i][j]=m[i-pg[k]][j-rune[k]]*dps[k]；
}
}
else
{
t=1,num=0；
while(num<s[k])
{
pg1=t*pg[k]；
rune1=t*rune[k]；
dps1=mi(dps[k],t)；
for(i=p；i>=1；i--)
for(j=r；j>=1；j--)
{
if(i<pg1 || j<rune1)
break；
if(m[i-pg1][j-rune1]*dps1>m[i][j])
m[i][j]=m[i-pg1][j-rune1]*dps1；
}
num+=t；
if(s[k]-num<t*2)
t=s[k]-num；
else
t*=2；
}
}
}
return m[p][r]；
}
int main()
{
int i,j；
double re；
scanf("%d %d %d\n",&n,&p,&r)；
for(i=1；i<=n；i++)
{
scanf("%d %d %d %d\n",&pg[i],&rune[i],&s[i],&j)；
dps[i]=((double)j)/100；
}
re=dp()；
re*=100；
printf("%.4f\n",re)；
}
type
item=record
cp,cr,s:integer；dps:extended；
end；
var
N,P,R,i,j,l,ip,si,k:integer；
buf:item；b,mf:extended；
it:array[1..4800] of item；
f:array[0..100,0..100] of extended；
procedure sf(i1,i2:integer；v:double)；
begin
if(i1>P)then exit；
if(i2>R)then exit；
if(f[i1,i2]<v)then
begin
f[i1,i2]:=v；
if(mf<v)then mf:=v；
end；
end；
function ft(base:double；time:integer):double；
var
cl:integer；
begin
ft:=base；
for cl:=2 to time do
ft:=ft*base；
end；
procedure ai(cp,cr:integer；dps:extended；s:integer)；
begin
inc(ip)；
it[ip].cr:=cr；
it[ip].cp:=cp；
it[ip].dps:=dps；
it[ip].s:=s；
end；
begin
mf:=1；
readln(N,P,R)；
ip:=0；
for i:=1 to N do
begin
readln(buf.cp,buf.cr,buf.s,buf.dps)；
if(buf.dps<100)then continue；
buf.dps:=buf.dps/100；
if(buf.s>0)then
begin
k:=1；
while k<buf.s do
begin
ai(buf.cp*k,buf.cr*k,ft(buf.dps,k),k)；
buf.s:=buf.s-k；
k:=k*2；
end；
if(buf.s>0)then
ai(buf.cp*buf.s,buf.cr*buf.s,ft(buf.dps,buf.s),buf.s)；
end
else
ai(buf.cp,buf.cr,buf.dps,0)；
end；
for i:=0 to p do
for j:=0 to r do
f[i,j]:=0；
f[0,0]:=1；
for i:=1 to ip do
begin
if(it[i].s>0)then
for j:=p-it[i].cp downto 0 do
for k:=r-it[i].cr downto 0 do
begin
if(f[j,k]>0)then sf(j+it[i].cp,k+it[i].cr,f[j,k]*it[i].dps)；
end
else
begin
for j:=0 to p-it[i].cp do
for k:=0 to r-it[i].cr do
if(f[j,k]>0)then sf(j+it[i].cp,k+it[i].cr,f[j,k]*it[i].dps)；
end；
end；
writeln((mf*100):0:4)；
end.
标程.....