刷题记录:牛客NC19990[HAOI2012]音量调节

传送门:牛客

题目描述:

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变
一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。
每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉
他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i
首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
输入:
3 5 10               
5 3 7
输出:
10

emmm,虽然是省选题,但是应该只是签到题的难度

主要思路:

1. 首先我们观察一下我们的数据范围,才1000,说明这道题我们可以乱搞了.所以我决定直接使用双重循环.我们可以使用$dp[i][j]$来记录经过了$i次更改音量,j音量是否能达到$
2. 那么我们的转移方程也不难写出.我们直接枚举$i-1$轮有哪些数字是可以组成的.那么我们现在在这些数字的基础上更改音量也肯定是能组成的(前提是不超过max_level,和不小于0)
3. 注意我们的更改音量是既可以增加也可以减少的
4. 对于我们的-1的情况,我们只要在枚举过程中判断是否有数字合法即可,加个flag就行

在搞清楚上述内容之后,我们的代码也就不难写出了

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,begin_level,max_level;
int a[maxn];
int dp[2000][100];
int main() {
	n=read();begin_level=read();max_level=read();
	for(int i=1;i<=n;i++) {
		a[i]=read();
	}
	dp[begin_level][0]=1;
	for(int i=1;i<=n;i++) {
		int flag=0;
		for(int j=0;j<=max_level;j++) {
			if(dp[j][i-1]) {
				if(j-a[i]>=0) {
					dp[j-a[i]][i]=1;
					flag=1;
				}
				if(j+a[i]<=max_level) {
					dp[j+a[i]][i]=1;
					flag=1;
				}
			}
		}
		if(flag==0) {
			printf("-1\n");
			return 0;
		}
	}
	for(int i=max_level;i>=0;i--) {
		if(dp[i][n]) {
			printf("%d\n",i);
			return 0;
		}
	}
	return 0;
}