本文共 2223 字，大约阅读时间需要 7 分钟。
题解：
简单的dp。 也许dp我只会做这种小白型的了我们发现他最多会演唱50首歌曲，最大音调为1000。
开一个 d p [ 50 ] [ 1000 ] ， d p [ i ] [ j ] dp[50][1000]，dp[i][j] dp[50][1000]，dp[i][j]代表演唱到第i个物品的时候，能不能演唱出来音调为j的歌曲。 初始状态全是false，只有 d p [ 0 ] [ b e g i n L e v e l ] = t r u e dp[0][beginLevel]=true dp[0][beginLevel]=true转移方程：
{ d p [ i ] [ j ] = d p [ i − 1 ] [ j + a [ i ] ] j + a [ i ] < = m a x m L e v e l ， d p [ i − 1 ] [ j + a [ i ] ] = = t r u e d p [ i ] [ j ] = d p [ i − 1 ] [ j − a [ i ] ] j − a [ i ] > = 0 , d p [ i − 1 ] [ j − a [ i ] ] = = t r u e \left\{\begin{matrix}dp[i][j]=dp[i-1][j+a[i]]&j+a[i]<=maxmLevel，dp[i-1][j+a[i]]==true\\dp[i][j]=dp[i-1][j-a[i]]&j-a[i]>=0,dp[i-1][j-a[i]]==true\ \end{matrix}\right. { dp[i][j]=dp[i−1][j+a[i]]dp[i][j]=dp[i−1][j−a[i]]j+a[i]<=maxmLevel，dp[i−1][j+a[i]]==truej−a[i]>=0,dp[i−1][j−a[i]]==true
代码：
#include#define int long long#define endl '\n'const int maxn=1010;using namespace std;const int mod=1e9+7;bool dp[55][maxn];int a[maxn];signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,st,ed; cin>>n>>st>>ed; for(int i=1;i<=n;i++) cin>>a[i]; dp[0][st]=true; for(int i=1;i<=n;i++){ for(int j=0;j<=ed;j++){ if(dp[i-1][j]){ if(j+a[i]<=ed) dp[i][j+a[i]]=true; if(j-a[i]>=0) dp[i][j-a[i]]=true; } } } int ans=-1; for(int i=0;i<=ed;i++){ if(dp[n][i]) ans=i; } cout< <
但是我们发现，dp[i][j]只有dp[i-1][j]这一维推过来，所以我们可以把数组滚动一下！
#include#define int long long#define endl '\n'const int maxn=1010;using namespace std;const int mod=1e9+7;bool dp[2][maxn];int a[maxn];signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,st,ed; cin>>n>>st>>ed; for(int i=1;i<=n;i++) cin>>a[i]; dp[0][st]=true; for(int i=1;i<=n;i++){ for(int j=0;j<=ed;j++){ if(dp[(i&1)^1][j]){ if(j+a[i]<=ed) dp[(i&1)][j+a[i]]=true; if(j-a[i]>=0) dp[(i&1)][j-a[i]]=true; dp[(i&1)^1][j]=false; } } } int ans=-1; for(int i=0;i<=ed;i++){ if(dp[(n&1)][i]) ans=i; } cout< <
转载地址：https://blog.csdn.net/xxxxxiao123/article/details/115680908 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
