当前位置: 代码迷 >> 综合 >> 1339 矿泉水
  详细解决方案

1339 矿泉水

热度:41   发布时间:2023-10-09 10:07:01.0

Description

  小PP对广大的矿泉水都爱的深沉。不过他对每个牌子的矿泉水都有不同的喜爱值。比如说对于第i种矿泉水,小PP对它的喜欢值为Ai。如果他在第k天喝了瓶第i种牌子的矿泉水,那么他在k+Ai天前(包括第k+Ai天)必须再喝一瓶这种牌子的矿泉水,否则就会精神失常。(Hint:如果第i种矿泉水的Ai=1,则小PP天天都要喝这种矿泉水,不然就会精神失常)。
  可是小PP又有个很奇怪得癖好,一天只喝一个牌子的水,或者他不喝。在第1天前,小PP因为太渴,把所有牌子(除了Evian)的矿泉水都喝了个遍。
  当然,每种牌子的矿泉水的价格都是不同的。不过这些牌子中有个叫Evian的牌子,喝他一次,便能得到永生。不过Evian超贵,一般人是喝不起的。但是唯一的希望是某个钱人送他一瓶。
  而这个有钱人将在特定的一天出现,他的出现,会带给小PP永生。若第i天小PP喝任何牌子的水都会精神失常,则认定:小PP最多正常i-1天。当然,小PP也是爱钱的,若他第i天不管喝任何水(不包括Evian)都会精神失常,那么,他在第i天是不会喝水的。(简单的说,先要命,后要钱)

Input

  第一行:n,m,q 表示共n种矿泉水,cp将在第m天出现,并送小PP一瓶Evian.(只要撑到第m天,即安全度过第m-1天,即可得到永生)
  小PP初始有q块大洋。
  第二行n个数: 表示喜爱值Ai
  第三行n个数: 表示第i个牌子的矿泉水单价 Ci元(这里的矿泉水不包含Evian)

Output

  若小PP能得到永生,则
  第一行:输出“+oo”(不含引号)。
  第二行:输出得到永生时小PP能剩下的最多钱数。
  否则,如果小PP不能得到永生,则
  第一行:输出小PP最多能精神正常得天数NMAX(就是不精神失常的天数)。
  第二行:输出小PP正常活到NMAX天能剩下的最多钱数。

Sample Input

【输入样例1】
4 4 1000
3 3 3 3
1 1 1 1
【输入样例2】
4 3 1000
3 3 3 3
1 1 1 1
【输入样例3】
2 4 7
2 3
1 1

Sample Output

【输出样例1】
2
1000
【输出样例2】
+oo
1000
【输出样例3】
+oo
5

Hint

【数据规模】
  50% n<=3
  80% A4<=4
  100% n<=4 q,Ci<=maxlongint m<=1000 Ai<=9

算法讨论

五维dp,f[i,j,k,e,r]表示在第i天是j天内必须和第一种水,后面同理,第i天可以不和或者喝任意一种水,所以上一次喝某种水且能活到今天的日期内买这种水。
varf:array[0..1100,0..9,0..9,0..9,0..9] of longint;x,y:array[0..10] of longint;n,m,q,i,j:longint;
function min(x,y:longint):longint;
beginif x>y then exit(y);exit(x);
end;
procedure chp;
vara:array[0..1000,0..9] of longint;p:longint;
beginfillchar(a,sizeof(a),$7);a[0,x[1]]:=0;for i:=1 to m dobeginfor j:=0 to x[1]-1 doa[i,j]:=min(a[i-1,j+1],a[i,j]);for j:=1 to x[1] doif i-j>=0 thena[i,x[1]]:=min(a[i,i-j]+y[1],a[i,x[1]]);end;p:=maxlongint;for i:=0 to x[1] dop:=min(p,a[m,i]);writeln('+oo');writeln(q-p);
end;
procedure xi;
vara:array[0..1000,0..9,0..9] of longint;tot,ans,k,l:longint;p:boolean;
beginfillchar(a,sizeof(a),$7);a[0,x[1],x[2]]:=0;for i:=1 to m-1 dobeginp:=false;ans:=tot;tot:=maxlongint;for j:=1 to x[1] dofor k:=1 to x[2] dobegina[i,j,k]:=a[i-1,j+1,k+1];for l:=1 to x[1] doa[i,j,k]:=min(a[i,j,k],a[i-1,l,k+1]+y[1]);for l:=1 to x[2] doa[i,j,k]:=min(a[i,j,k],a[i-1,j+1,l]+y[2]);if (j>0)and(k>0) thenbeginif a[i,j,k]<=q then p:=true;if a[i,j,k]<tot then tot:=a[i,j,k];end;end;if p=false thenbeginwriteln(i-1);writeln(q-ans);halt;end;end;writeln('+oo');writeln(q-tot);
end;
procedure huan;
vara:array[0..1000,0..9,0..9,0..9] of longint;tot,ans,k,l,e:longint;p:boolean;
beginfillchar(a,sizeof(a),$7);a[0,x[1],x[2],x[3]]:=0;for i:=1 to m-1 dobeginp:=false;ans:=tot;tot:=maxlongint;for j:=1 to x[1] dofor k:=1 to x[2] dofor e:=1 to x[3] dobegina[i,j,k,e]:=a[i-1,j+1,k+1,e+1];for l:=1 to x[1] doa[i,j,k,e]:=min(a[i,j,k,e],a[i-1,l,k+1,e+1]+y[1]);for l:=1 to x[2] doa[i,j,k,e]:=min(a[i,j,k,e],a[i-1,j+1,l,e+1]+y[2]);for l:=1 to x[3] doa[i,j,k,e]:=min(a[i,j,k,e],a[i-1,j+1,k+1,l]+y[3]);if (j>0)and(k>0)and(e>0) thenbeginif a[i,j,k,e]<=q then p:=true;if a[i,j,k,e]<tot then tot:=a[i,j,k,e];end;end;if p=false thenbeginwriteln(i-1);writeln(q-ans);halt;end;end;writeln('+oo');writeln(q-tot);
end;
procedure zxy;
vartot,ans,k,l,e,r:longint;p:boolean;
beginfillchar(f,sizeof(f),$7);f[0,x[1],x[2],x[3],x[4]]:=0;for i:=1 to m-1 dobeginp:=false;ans:=tot;tot:=maxlongint;for j:=1 to x[1] dofor k:=1 to x[2] dofor e:=1 to x[3] dofor r:=1 to x[4] dobeginf[i,j,k,e,r]:=f[i-1,j+1,k+1,e+1,r+1];for l:=1 to x[1] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,l,k+1,e+1,r+1]+y[1]);for l:=1 to x[2] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,j+1,l,e+1,r+1]+y[2]);for l:=1 to x[3] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,j+1,k+1,l,r+1]+y[3]);for l:=1 to x[4] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,j+1,k+1,e+1,l]+y[4]);if (j>0)and(k>0)and(e>0)and(r>0) thenbeginif f[i,j,k,e,r]<=q then p:=true;if f[i,j,k,e,r]<tot then tot:=f[i,j,k,e,r];end;end;if p=false thenbeginwriteln(i-1);writeln(q-ans);halt;end;end;writeln('+oo');writeln(q-tot);
end;
beginreadln(n,m,q);for i:=1 to n doread(x[i]);for i:=1 to n doread(y[i]);if n=1 then chp;if n=2 then xi;if n=3 then huan;if n=4 then zxy;
end.