背包变形:过程型背包

过程型背包简单的感觉就是我要记录下是否回到这种情况，也就是说要记录一个最大到达的可能值或者是一个最小到达的可能值

#例1 P1877 [HAOI2012]音量调节

胡乱分析

上来bfs得60分。。。
dp的思路就是我看看我能最终到达的最大音量是多少，每一步都有两种可能性，也就是我要加音量或者我要减当前的音量所以我们思路就是:
for i->[1,n] (这里表示我们总共弹奏的歌曲数)
for j->[0,maxn] (这里表示我们j从0枚举到最大值)
if dp[i-1][j]
dp[i][j+num[i]]=dp[i][j-num[i]]=1 (这里表示我们如果上一个音量是合法的那么我们把他所能表示出来的音量也标记为合法的)

代码

#include <bits/stdc++.h>
using namespace std;
int num[6666],dp[6666][6666];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,begin,maxn;
  cin>>n>>begin>>maxn;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  dp[0][begin]=1;
  for(int i=1;i<=n;i++)
  for(int j=0;j<=maxn;j++)
  {
    if(dp[i-1][j])
    dp[i][j+num[i]]=dp[i][j-num[i]]=1;
  }
  for(int i=maxn;i>=0;i--)
  if(dp[n][i])
  return cout<<i,0;
  cout<<-1;
}

例2 待补充