牛客刷题记录（四）

题记录（四）"/>

牛客刷题记录（四）

【快手】最少数量货物装箱问题

题目地址
知识点：动态规划
解题思路:
1.动态规划
状态转移方程：dp[i] = min(dp[i-3], dp[i-5], dp[i-7]) + 1
我们初始化1 - 7的dp数组，可以装满的重量状态初始化为最小数量，如果不能装满就初始化为100001，标志无法走通。
如果总重量N是(3, 5, 7)是其中至少任意一个数的倍数，那么此路径可以走通，是一个小于100001的值，如果大于等于100001，那么无法装满
2.（3， 5， 7）的最小公倍数是105，只要可以整除105，那么就可以装满，105最少装满的数量是15。最终余数小于105，可以直接穷举法求解，复杂度也不会很高。
3. 这个很难想到，是评论区大哥的思路：
对7取余，对余数进行讨论即可
余数为1,3,5，则可以装满，1可以视为1+7=3+5，依旧是之前的count+1
余数为2,4,6，也可以装满，2可以视为2+7=3+3+3，4可以视为4+7=5+3+3，6=3+3是之前的count+2

#include <bits/stdc++.h>
using namespace std;
#define MAX 10001
int main()
{int x;cin >> x;vector<int> dp(x+1, MAX);dp[3] = 1;dp[5] = 1;dp[6] = 2;dp[7] = 1;for (int i = 8; i <= x; i++){dp[i] = min(dp[i-3], min(dp[i-5], dp[i-7])) + 1;}cout << (dp[x] >= MAX? -1: dp[x]) << endl;
}

【快手】最长回文子串

题目地址
知识点：动态规划，回文子串
解题思路：
1.题目十分经典，就是动态规划
2.或者采用从中心扩散的思路，注意考虑对称的情形
3.还有著名的马拉车算法

还有一个之前做过的最长不连续回文子串，那道题也是采用动态规划求解
dp[i][j] = dp[i+1][j-1]+2 if str[i] == str[j]
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) if str[i] != str[j]

#include <bits/stdc++.h>
using namespace std;int main()
{string str;cin >> str;vector<vector<bool>> dp(str.size(), vector<bool>(str.size(), false));int cnt = 0;for (int i = str.size()-1; i >= 0; i--)for (int j = i; j < str.size(); j++){if (j - i < 2 && str[i] == str[j])dp[i][j] = true;if (j - i >= 2 && str[i] == str[j] && dp[i+1][j-1])dp[i][j] = true;if (dp[i][j])cnt++;}cout << cnt << endl;
}

【快手】连续子数组最大值

题目地址
知识点：动态规划
解题思路：也是十分经典的动态规划题目

#include <bits/stdc++.h>using namespace std;int main()
{vector<int> nums;int num;while(cin >> num){nums.push_back(num);char c = getchar();if(c=='\n')break;}int dp[nums.size()];dp[0] = nums[0];int res = nums[0];for (int i = 1; i < nums.size(); i++){if (dp[i-1] > 0)dp[i] = dp[i-1] + nums[i];elsedp[i] = nums[i];res = max(res, dp[i]);}cout << (res > 0? res: 0) << endl;
}