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

NC15891-iko和她的糖

题目链接

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

题目描述

iko超级超级喜欢吃糖，有一天iko想出去玩，她计划从1点走到N点（按1,2,3，...，n的顺序走），每个点都有一个补给站，第i点的补给站有a[i]颗糖，从i点走到i+1点会消耗掉b[i]颗糖，iko在出游的途中可以选择三个补给站，iko想知道她走完全程到达N点时口袋里最多还能剩下几颗糖（初始时iko的口袋里一颗糖都没有）。

第一行输入N（3<=N<=1000）
第二行输入N个数代表a[1].......a[N] (0<=a[i]<=1000 )
第三行输入N-1个数代表b[1]......b[N-1] ( 0<=b[i]<=1000 )

输出一个数字表示iko到达n点时口袋里最多剩下的糖，若不能到达N点输出-1。

测试样例

样例1

输入

3
1 3 4
3 4

输出

-1

样例2

输入

5
3 4 5 2 4
3 2 2 2

输出

3

解题思路

dfs剪枝就可以，根据题意我们知道每一个站点都会经过一次所以每一次都要花费一定的糖，到达站点以后iko可以选择那这个站点的糖或者不拿（dfs两个不同方向的搜索）。同时剪枝的条件是当到达某个站点后剩余糖数是负数，说明他不能到达这个站点，也就走不到这里所以就停止，或者拿糖次数一定多于3次了，那么也停止。当他可以到达13号站点时说明他可以到达终点，那么用max统计不同到达终点策略最后剩下的最多糖数即可。

解题代码

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

const int N = 1e5;
int ans = -1;
//存储获取糖的数量，以及达到这个站点消耗的糖的数量
int a[N], b[N];
int n;

//当下剩余的糖的数量，所处站点编号，已经拿过糖的次数
void dfs(int extra, int x, int c)
{
    //如果拿糖次数>3
    //或者剩余糖的数量<0,说明到达不了这个站点
    if (c > 3 || extra < 0)
    {
        //退出
        return;
    }
    //如果到达了n+1，那么就走完了，统计糖的个数
    if (x == n + 1)
    {
        ans = max(ans, extra);
        return;
    }
    //去往下一个站点，并且此次站点不拿糖
    dfs(extra - b[x], x + 1, c);
    //去往下一个站点，并且此次站点拿糖
    extra += a[x];
    dfs(extra - b[x], x + 1, c + 1);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++)
    {
        cin >> b[i];
    }
    dfs(0, 1, 0);
    cout << ans << endl;
    system("pause");
    return 0;
}

NC15613-K序列

题目链接

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

题目描述

给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度，满足这个序列是 K 序列。链接：

第一行为两个整数 n, K, 以空格分隔，第二行为 n 个整数，表示 a[1] ∼ a[n]，1 ≤ n ≤ 105 , 1 ≤ a[i] ≤ 109 , 1 ≤ n，K ≤ 107 。输出一个整数表示最长子序列的长度 m。

测试样例

输入

7 5
10 3 4 2 2 9 8

输出

6

解题思路

dp,一如既往地大脑空白，就当总结题型了，其实这道题和《被3整除的子序列》这道题有相同的思路，可以作为参考。我们每次取一个数，假设为num[i]，并且声明两个数组，dp[j]表示的是加上num[i]以后模k余数为j的最长子序列的长度，temp[h]表示的是在未加num[i]之前余数为h的最长子序列的长度。那么我们很容易得到一个递推式：
即cnt=(num[i]+j)%k,那么dp[cnt]即余数为cnt的最长子序列长度就等于temp[j]+1即等于余数为j的最长子序列的长度+1。但是我们要注意几个细节：

• 如果temp[j]==0，那么也就是说明在num[i]之前的所有数无论怎么组合也凑不来余数为j的子序列，那么很显然余数为(num[i]+j)%k的子序列也凑不来，所以跳过上面的递归式
• 但是如果temp[j]==0时又满足j==0，那么此时（num[i]+j)%k的子序列至少可以增加一个长度，即只取num[i]自己组成一个单位长度的子序列就满足num[i]%k==0，所以可以进入上面的递归式
• 每一次检验完一个数以后，dp[j]的长度可能大于或等于temp[j]，所以我们需要更新temp数组

解题代码

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

const int maxn = 1e5 + 5;
const int maxk = 1e7 + 5;
//假设我们取的下一个数是num[i]
//temp[j]表示在num[i]之前的所有数中所能凑出的余数为j的最长子序列的长度
int temp[maxk];
//dp[j]表示在加上num[i]以后余数为j的子序列的最大长度
int dp[maxk];
//存储数值
int num[maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    for (int i = 0; i < n; i++)
    {
        //j==0时可以进入，因为至少存在一个只取num[i]自己组成一个单位长度的子序列使得余数为(0+num[i])%k的子序列长度+1
        //temp[j]==0时不可以进入，因为此时就不存在能凑出来所需要的余数为j的子序列
        //那么相应的余数为(j+num[i])%k的子序列肯定也不存在，所以就不用加一了
        for (int j = 0; j < k; j++)
        {
            if (j == 0 || temp[j] != 0)
                dp[(j + num[i]) % k] = temp[j] + 1;
        }
        //每次检查完num[i]以后
        //dp>=temp,所以我们需要更新temp
        for (int j = 0; j < k; j++)
            temp[j] = max(temp[j], dp[j]);
    }
    cout << temp[0] << endl;
}