[HAOI2012] 音量调节

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中整数 $beginLevel$，代表吉他刚开始的音量，整数 $maxLevel$，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $maxLevel$。输入中还给定了 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数 $n$，$beginLevel$ 和 $maxLevel$。

第二行依次为 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$。

输出格式

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 $0$ 或者高于 $maxLevel$，输出 -1。

样例 #1

样例输入 #1

1
2
3 5 10
5 3 7

样例输出 #1

1
10

提示

$1\le n\le 50$，$1\le c_i\le maxLevel$，$1\le maxLevel\le 1000$，$0\le beginLevel\le maxLevel$。

题解

题目解析

一道另类的背包题目, 到达型的背包. 类似于二分答案的到达型解法. 一句话总结就是把所有的可能到达的结果都跑一遍.

定义一个数组dp[i][j]=第i个歌曲是否可以凑成j的音乐(1为可以,0则不可以)

接着是这样考虑的:

很好理解, 前面可以组成 $j-a[i]$ 的时候我们可以加上 $a[i]$ 凑成 $j$ 然后把关于 $j$ 的dp数组设置成 $1$ . 如果是 $j + a[i]$ 则是在之前的结果上减去 $a[i] $.

这样我们遍历从 $0$ 到 $maxLevel$ 就完事了, 最后输出相应的值就可了.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;

MAXN(1000);
int a[MAXN],dp[100][MAXN];

signed main(){
	CIN_;CIN;
	int n,b,m;
	cin >> n >> b >> m;
	dp[0][b] = 1;
	fa(i,1,n) cin >> a[i];
	fa(i,1,n){
		fb(j,m,0){
			if(j - a[i] >= 0 && dp[i-1][j - a[i]]) dp[i][j] = 1;
			if(a[i] + j <= m && dp[i-1][j + a[i]]) dp[i][j] = 1;
		}
	}
	fb(i,m,1){
		if(dp[n][i]){
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Remark

我在考虑的时候, 想把它用 $n \% 2$ 压缩, 这样可以只开 $2$ 个维. 但是事实上我们在转移的时候, 之前的状态被正确转移. 但是上上次的状态同时也存在在里面, 于是我想到另外一个解决方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fa(i,1,n){
    int p = i % 2;
    fb(j,m,0){
        dp[p%2][j] = 0;//这里是关键步骤
        if(j - a[i] >= 0 && dp[(p+1)%2][j - a[i]]) dp[p][j] = 1;
        if(a[i] + j <= m && dp[(p+1)%2][j + a[i]]) dp[p][j] = 1;
    }
}
fb(i,m,1){
    if(dp[n%2][i]){
        cout << i << endl;
        return 0;
    }
}