[HAOI2012]音量调节题解

/*
该问题可转化为01背包的二维数组(数据较少可用)，一维滚动数组不好操作

1.dp数组含义
	dp[i][j]表示第i首歌时，j为其音量大小，如果0<=j<=maxLevel,则令dp[i][j]=1，否则为0
2.递推公式---当前音量共两种情况，之前一首歌的音量加或减列表中要改变的音量
	if(j+nums[i]<=maxLevel) 
		dp[i][j]=dp[i][j]||dp[i-1][j+nums[i]];
	if(j>=nums[i]) 
		dp[i][j]=dp[i][j]||dp[i-1][j-nums[i]];
3.初始化
	dp[0][beginLevel]=1,如果dp[0][beginLevel] = 0 的话，后⾯所有推导出来的值都是0了.剩余也初始化成0，
4.遍历

图解：
							j
	0	1	2	3	4	5	6	7	8	9	10
 i
 0      0	0	0	0	0	1	0	0	0	0	0
歌1     1	0	0	0	0	0	0	0	0	0	1
歌2     0	0	0	1	0	0	0	1	0	0	0
歌3     1	0	0	0	0	0	0	0	0	0	1

nums[]={5,3,7},beginLevel=5,maxLevel=10;
*/


#include<bits/stdc++.h>
using namespace std;

int n, beginLevel, maxLevel;

int main() {
  cin >> n >> beginLevel >> maxLevel;

  vector<int> nums(n + 1);
  for (int i = 1;i <= n;i++)
      cin >> nums[i];

  vector<vector<int>> dp(n + 1, vector<int>(maxLevel + 1, 0));
  dp[0][beginLevel] = 1;

  for (int i = 1;i <= n;i++) 
      for (int j = 0;j <= maxLevel;j++) {
          if (j + nums[i] <= maxLevel)
              dp[i][j] = dp[i][j] || dp[i - 1][j + nums[i]];
          if (j >= nums[i]) 
              dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
      }

  int tmp = -1;
  // 从最后一行开始，从后往前遍历
  for (int i = maxLevel;i >= 0;i--) 
      if (dp[n][i]){
          tmp = i;
          break;
      }
  cout << tmp;

  return 0;
}