[ABC095C] Half and Half
a,b,c=ab*2三種披薩，目標是x個a披薩，y個b披薩 。
結(jié)論：設最優(yōu)解是a,b,c披薩各u,v,w個（價格最低），則?u,v,w至少有一個為零！?
反證法：設u,v,w都大于零，則
在a+b>=c情況下可以加一個c，少一個a和b?
在a+b<=c情況下可以少一個c，多一個a和b?
基于上述的結(jié)論，最優(yōu)策略一定屬于以下三者之一?
不買c的策略(w=0)，代價為noc = a*x+b*y;?
不買a的策略(u=0)，代價為noa = c*x+b*max(y-x,0)?
不買b的策略(v=0)，代價為nob = c*y+a*max(x-y,0)
標簽：
