Description

一个吉他手准备参加一场演出. 他不喜欢在演出时始终使用同一个音量, 所以他决定每一首 歌之前他都要改变一次音量. 在演出开始之前, 他已经做好了一个列表, 里面写着在每首歌 开始之前他想要改变的音量是多少. 每一次改变音量, 他可以选择调高也可以调低.

音量用一个整数描述. 输入文件中给定整数 \(beginLevel\), 代表吉他刚开始的音量, 以及 整数 \(maxLevel\), 代表吉他的最大音量. 音量不能小于 \(0\) 也不能大于 \(maxLevel\). 输入文件中还给定了 \(n\) 个整数 \(C_1, C_2, C_3, \ldots, C_n\), 表示在第 \(i\) 首歌 开始之前吉他手想要改变的音量是多少.

吉他手想以最大的音量演奏最后一首歌, 你的任务是找到这个最大音量是多少.

Input

第一行依次为三个整数:\(n, beginLevel, maxLevel\).

第二行依次为 \(n\) 个整数:\(C_1, C_2, C_3, \ldots, C_n\).

Output

输出演奏最后一首歌的最大音量. 如果吉他手无法避免音量低于 \(0\) 或者高于 \(maxLevel\), 输出 \(-1\).

Sample Input

3 5 10
5 3 7

Sample Output

10

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 50, 1 \leq C_i \leq maxLevel, 0 \leq beginLevel \leq maxLevel \leq 1000\)

Explanation

当然就是一个 \(O(n \times maxLevel)\) 的动规啦......

跟着 @xmcp 做了两道题, 发现此题好水, 居然也标榜省选题 2333

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 60, maxm = 1010;

int n, b_lev, mx_lev;
int val[maxn], dp[maxn][maxm];

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &b_lev, &mx_lev);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]);
    dp[0][b_lev] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= mx_lev; j++) {
            if (j + val[i] <= mx_lev) {
                if (dp[i - 1][j + val[i]])
                    dp[i][j] = true;
            } if (j - val[i] >= 0) {
                if (dp[i - 1][j - val[i]])
                    dp[i][j] = true;
            }
        }
    // Getting result
    int res = -1;
    for (int j = 0; j <= mx_lev; j++)
        if (dp[n][j])
            res = j;
    printf("%d\n", res);
    return 0;
}