P1877 HAOI2012 音量调节
可行性背包
思路
把状态方程的性质设置为可行性，即要么可行，要么不可行。
定义状态方程\(F[i][j]\)表示前\(i\)首歌能否到达音量\(j\)。
那么状态转移方程则是
\(F[i][j] = F[i][j] || F[i - 1][j - w[i]]\)
\(F[i][j] = F[i][j] || F[i - 1][j + w[i]]\)
代码实现
状态转移初始化
F[0][beginLevel] = 1;
即把达到初始音量的可行性赋值为1。
状态转移实现
for (int i = 1; i <= n; i++)
{
for (int j = maxLevel; j >= 0; j--)
{
if (F[i - 1][j] && j + c[i] <= maxLevel)
{
F[i][j + c[i]] = 1;
}
if (F[i - 1][j] && j - c[i] >= 0)
{
F[i][j - c[i]] = 1;
}
}
}
从高到低找答案
for (int i = maxLevel; i >= 0; i--)
{
if (F[n][i] == 1)
{
cout << i;
return 0;
}
}