bzoj 4380 [POI2015]Myjnie

Posted by

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=4380

题解

首先将价格离散化一下,从小到大存入\(C[i]\)中。
区间DP:设\(f[i][j][k]\)表示区间\([i,j]\)中价格不小于\(k\)时的最大收益,\(g[i][j][k]\)表示区间\([i,j]\)中价格等于\(k\)时的最大收益情况时最便宜价格的洗车店位置,\(h[i][j]\)表示当前枚举区间中\(i\)位置费用限制不小于\(j\)的人数,\(pos[i][j][k]\)表示\(f[i][j][k]\)时的价格。
状态转移方程:
\[f[i][j][k]=max(max\{f[i][l-1][k]+f[l+1][r][k]+C[k]*h[l][k],\quad i\leq l\leq j\},\\
f[i][j][k+1])\]

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注