本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC19990-[HAOI2012]音量调节

题目链接

https://ac.nowcoder.com/acm/problem/19990

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i首歌开始之前吉他手想要改变的音量是多少。吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

第一行依次为三个整数：n, beginLevel, maxlevel。第二行依次为n个整数：c1,c2,c3…..cn。输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel，输出-1。

测试样例

输入

3 5 10               
5 3 7

输出

10

解题思路

我们知道第i+1演出时能够达到的音量是由第i次演出后所结束的音量决定。因此我们可以定义volum[i][j]数组表示第i次表演后能否到达的音量j，0表示不能，1表示可以，那么很明显就有如下递推式

也就是说如果第i次演奏后想要达到音量j+x，那么j+x必须小于最大音量并且第i-1次演奏后可以到达音量j,第i次演奏后想要达到音量j-x，那么j-x必须大于最小音量并且第i-1次演奏后可以到达音量j。所以很明显是一个二维dp，实际上我们发现dp大部分都是可以参考0/1背包dp思路的，全部都是打表思想并且永远是后者由前者决定，只不过每一次的递推条件不同，这个具体的变式思路只能够通过多练来积累。

解题代码

#include <bits/stdc++.h>
using namespace std;

//volum[i][j]表示的是在i此表演后能否到达音量j
//如果为1表示可以到达
//0表示无法到达
int volum[105][1005];

int main()
{
    int n, b, m;
    cin >> n >> b >> m;
    //未开始演出时可以到达初始音量，所以置为1
    volum[0][b] = 1;
    for (int i = 1; i <= n; i++)
    {
        //对于每一次的音量调节大小x
        int x;
        cin >> x;
        //注意枚举表演i首后能否到达音量j
        //因为还是二维0/1dp没有降维，所以j正序逆序都可以
        for (int j = 0; j <= m; j++)
        {
            //当且仅当j+x没有超出最大音量，且在表演i-1次后音量可以到达j时
            //表演第i首歌以后才可以到达j+x音量
            if (j + x <= m && volum[i - 1][j])
                volum[i][j + x] = 1;
            //当且仅当jxx没有超出最小音量，且在表演i-1次后音量可以到达j时
            //表演第i首歌以后才可以到达j-x音量
            if (j - x >= 0 && volum[i - 1][j])
                volum[i][j - x] = 1;
        }
    }
    //但是注意最终要求的是寻找表演n次后可以到达的最大音量
    //所以此时i必须为逆序的
    for (int i = m; i >= 0; i--)
    {
        //一定是volum[n][i]因为必须表演完n次
        if (volum[n][i])
        {
            //第一个出现的1值就是可以到达的最大音量
            //输出这个最大音量i即可
            cout << i << endl;
            system("pause");
            return 0;
        }
    }
    //如果整个第n行都是0，说明无法表演完n首歌，所以输出-1
    cout << "-1" << endl;
    system("pause");
    return 0;
}

NC21467-货币系统

题目链接

https://ac.nowcoder.com/acm/problem/21467

题目描述

在网友的国度***有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b) 与原来的货币系统(n,a)等价，且m尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。输入的第一行包含一个整数T,表示数据组数。接下来按照如下格式分别给出T组数据。每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。

测试样例

输入

2
4
3 19 10 6
5
11 29 13 19 17

输出

2
5

说明

在第一组数据中，货币系统(2, [3,10])和给出的货币系统(n, a)等价，并可以验证不存在m < 2的等价的货币系统，因此答案为2。
在第二组数据中，可以验证不存在m < n的等价的货币系统，因此答案为5。

解题思路

首先我们很容易想到货币系统之所以可以减少货币数量，是因为给出的某些货币可以由更小的货币组成，比如样例1中的19可以由货币10+3+6组成，所以我们可以得到一个关系，价值大的货币是否可有可无主要取决于能否被小货币组合表示。因此我们定义vis数组，0表示不能被其他小货币表示，1表示可以被其他小货币表示即可有可无。那么我们将货币按价格有小到大排序，对于每一个货币k，如果他可以被表示，那么对于由k和其他货币a[i]组成的货币价格k+a[i]肯定也是可以被表示的。

解题代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
//存储货币
int a[105];
//vis标记数组
//0表示不可以被其他货币表示
//1表示可以被其他货币表示也就可有可无
int vis[N];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        //初始化
        memset(a, 0, sizeof(a));
        memset(vis, 0, sizeof(vis));
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        //排序
        sort(a + 1, a + n + 1);
        //默认每一个货币都是必须存在的
        int ans = n;
        //首先0肯定是可有可无的
        vis[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            //如果vis为1，那么这个货币可有可无
            //货币数量-1
            if (vis[a[i]])
            {
                ans--;
            }
            //否则这个货币必须存在
            //然后所有可以表示的货币值j+a[i]肯定也就是可以被表示了
            //都标记为1表示可有可无
            for (int j = 0; j <= a[n]; j++)
            {
                //枚举j从a[i]到最大货币值
                //如果j是可以被表示的
                if (vis[j])
                {
                    //那么j+a[i]肯定也可以被表示
                    vis[j + a[i]] = 1;
                }
            }
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}