问题描述
你将要在元旦演奏一场吉他专场。但你不希望声音平淡，所以你希望每个曲之间都有变化。现在你已经确定了每个曲可以与上一个曲之间的音量的变化量，即每首曲开始，你可以对音量选择增加或减少一个指定的变化值。当然音量不可能为负数，也不能太高，因此必需保证每首曲音量在0和maxLevel之间（包含）。
你的任务是，根据已有的开始音量beginLevel 和每首曲之间的变化量，求出最后一首曲的最大可能音量。如果没有方案，输出 -1。
输入
第一行有三个整数，n, beginLevel, maxLevel，分别表示曲目数，开始量，最大限制音量。
下面有n-1行整数，第i行整数表示第i首曲与第i+1首曲之间的变化量。
输出
只一行一个数，答案。
样例输入
【样例1】 4 5 10 5 3 7 【样例2】 5 8 20 15 2 9 10
样例输出 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\n",i); return 0; } printf("-1\n"); return 0; } /************************************************************** Language: C++ Result: 正确 Time:1 ms Memory:9900 kb ****************************************************************/
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-动态规划22-括号生成6812 人正在系统学习中
