变音量——动态规划

问题描述

你将要在元旦演奏一场吉他专场。但你不希望声音平淡，所以你希望每个曲之间都有变化。现在你已经确定了每个曲可以与上一个曲之间的音量的变化量，即每首曲开始，你可以对音量选择增加或减少一个指定的变化值。当然音量不可能为负数，也不能太高，因此必需保证每首曲音量在0和maxLevel之间（包含）。
你的任务是，根据已有的开始音量beginLevel 和每首曲之间的变化量，求出最后一首曲的最大可能音量。如果没有方案，输出 -1。

输入

第一行有三个整数，n, beginLevel, maxLevel，分别表示曲目数，开始量，最大限制音量。
下面有n-1行整数，第i行整数表示第i首曲与第i+1首曲之间的变化量。

输出

只一行一个数，答案。

样例输入

样例输出 Copy

【样例1】
10
【样例2】
-1

提示

1<=n<=60;
1<= maxLevel <=1000
0<= beginLevel <= maxLevel

刚开始上面还有dfs的做法但是发现并不能够在规定时间内通过，于是换了个方法，用DP来做

#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
//#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
#define read read()
const ll inf = 1e15;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
#define start int wuyt()
#define end return 0
int n,beginvalue,maxx,ans=-1;
int a[maxn],dp[1008][1008];
void dfs(int i,int temp)
{
    if(i==n)
    {
        if(temp>ans) ans=temp;
        return;
    }
    if(temp+a[i]<=maxx)
        dfs(i+1,temp+a[i]);
    if(temp-a[i]>=0)
        dfs(i+1,temp-a[i]);
}
int main()
{
    n=read,beginvalue=read,maxx=read;
    dp[1][beginvalue]=1;
    ///for(int i=1;i<n;i++) a[i]=read;
    for(int i=2;i<=n;i++) a[i]=read;
    for(int i=1;i<=n;i++)
        for(int j=maxx;j>=0;j--){
            if(j-a[i]>=0) dp[i][j]|=dp[i-1][j-a[i]];
            if(j+a[i]<=maxx) dp[i][j]|=dp[i-1][j+a[i]];
        }
    for(int i=maxx;i>=1;i--)
        if(dp[n][i]){
            printf("%d
",i);
            return 0;
        }
    printf("-1
");
    return 0;
}
 
/**************************************************************
    Language: C++
    Result: 正确
    Time:1 ms
    Memory:9900 kb
****************************************************************/