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

NC16600-接水问题

题目链接

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

题目描述

学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。

现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj 后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x秒结束时完成接水， 则k同学第x+1秒立刻开始接水。 若当前接水人数n不足m，则只有n个龙头供水，其它m−n个龙头关闭。

现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。第2行n个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi表示i号同学的接水量。请给出接水所需要的的总时间。1<=n<=10000,1<=m<=100并且m<=n,1<=wi<=100。

测试样例

样例1

输入

5 3 
4 4 1 2 1

输出

4

说明

第1 秒，3 人接水。第 1秒结束时，1、2、3 号同学每人的已接水量为 1，3 号同学接完水，4 号同学接替 3 号同学开始接水。
第2 秒，3 人接水。第 2 秒结束时，1、2 号同学每人的已接水量为 2，4 号同学的已接水量为 1。
第3 秒，3 人接水。第 3 秒结束时，1、2 号同学每人的已接水量为 3，4 号同学的已接水量为 2。4号同学接完水，5 号同学接替 4 号同学开始接水。
第4 秒，3 人接水。第 4 秒结束时，1、2 号同学每人的已接水量为 4，5 号同学的已接水量为 1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为4 秒。

样例2

输入

8 4 
23 71 87 32 70 93 80 76

输出

163

解题思路

就是正常的模拟，那么对于学生i，他要去接水的水龙头肯定是对于他的视角来说最早时间结束的，那么这个水龙头就要给学生i接水，相应的，他工作的时间就要+wi，所以我们枚举每一个学生i要去的最早结束的水龙头加上这个学生的用水时间w[i]，最终所有学生都接完水以后，我们遍历水龙头寻找最晚结束工作的水龙头即为答案。

解题代码

#include 
using namespace std;
const int N = 10005;
const int M = 105;
int a[M] = {}; //存储水龙头结束时间
int w[N] = {}; //存储每一个学生用水时间
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    for (int i = 1; i <= n; i++)
    {
        //将每一个学生都分给当下最早结束(即a[i]最小)的水龙头
        int idx = 1; //一定要注意是1
        for (int j = 1; j <= m; j++)
        {
            if (a[j] < a[idx])
                idx = j;
        }
        a[idx] += w[i];
    }
    //遍历所有水龙头
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        //寻找最晚结束的时间
        ans = max(ans, a[i]);
    }
    cout << ans << endl;
    system("pause");
    return 0;
}

NC19909-涂色PAINT

题目链接

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

题目描述

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。

例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。

输入仅一行，包含一个长度为n的字符串，即涂色目标。
字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

输出一个数表示需要的最少涂色次数。

测试样例

样例1

输入

AAAAA

输出

1

样例2

输入

RGBGR

输出

3

解题思路

区间dp,我们规定dp[l][r]表示为从左端点l涂色到右端点r的最少次数。那么就有以下规律：

• 如果l==r，即就一个字符，那么就涂色一次即可

• 如果l!=r，则l一定在r的左边

  1. 如果s[l]==s[r]即这个区间的字符串左端点颜色和右端点颜色相同，那么若要产生最少涂色次数，肯定是一次将左端点和右端点都涂色了，所以可以看成是给[l+1,r]区间涂色时顺带涂上了l，或者[l,r+1]区间涂色时顺带涂上了r，所以取这两个的最小值即可。公式为

     

  2. 如果s[l]!=s[r]，那么不可能一次将l,r全部涂色，肯定存在了一个后来被覆盖掉了的中间过渡节点k，填涂时是涂色[l,k]和[k+1,r]形成的，所以是两者之和，又因为k是l,r之间的节点，所以枚举k的情况，公式为

     

解题代码

#include 
using namespace std;
const int MAXN = 1e3 + 7;   //最大值
const int INF = 0x3f3f3f3f; //无穷大
int dp[MAXN][MAXN];         //从做端点到右端点区间部分填涂的最少次数
int main()
{
    string s; //存入字符串
    cin >> s;
    int len = s.length();                         //字符串长度
    s = ' ' + s; //将字符串预处理前面加一个字符，这样l从1开始更舒服
    memset(dp, INF, sizeof(dp));                  //将所有区间的填涂次数初始化为无穷大
    for (int length = 1; length <= len; length++) //枚举区间长度从1开始到len
    {
        for (int l = 1; l + length - 1 <= len; l++) //枚举左端点的开始处
        {
            //右端点就是左端点+长度-1
            int r = l + length - 1;
            //如果左右端点恰巧相同，那么就是一个字符，填涂一次即可
            if (length == 1)
                dp[l][r] = 1;
            else
            {
                //如果左端点，右端点颜色相同
                if (s[l] == s[r])
                    //那么填涂次数就等于dp[l+1][r]与dp[l][r-1]的最小者
                    dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
                else
                {
                    //否则必定逐渐还有一个过渡的填色点且他后来要被覆盖所以必定在l,r之间，枚举尝试
                    for (int k = 1; k < r; k++)
                    {
                        dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
                    }
                }
            }
        }
    }
    cout << dp[1][len] << endl;
    system("pause");
    return 0;
}