题解 | #[HAOI2012]音量调节#

题解：
简单的dp。
也许dp我只会做这种小白型的了（剩下的交给队友奥里给）
首先我们先看一下，不优化空间的dp怎么写的。

我们发现他最多会演唱50首歌曲，最大音调为1000。
开一个代表演唱到第i个物品的时候，能不能演唱出来音调为j的歌曲。
初始状态全是false，只有
转移方程：

代码：

#include <bits/stdc++.h>

#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<<ans<<endl;
}

但是我们发现，dp[i][j]只有dp[i-1][j]这一维推过来，所以我们可以把数组滚动一下！

#include <bits/stdc++.h>

#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<<ans<<endl;
}