牛客网OJ题解--20210301
A-神奇的数字
https://ac.nowcoder.com/acm/problem/14538
本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。
NC14538-神奇的数字
题目链接
https://ac.nowcoder.com/acm/problem/14538
题目描述
今天是Tabris和mengxiang000来到幼儿园的第6天，美丽的老师在黑板上写了几个数字：121,11,131，聪明的Tabris一眼就看出这些数字是那样的神奇——无论是正着写还是反着写都是一样的，mengxiang000想要得到更多的这样有趣的数，又因为这是二人到幼儿园的第6天，6+2=8。他们想知道长度为8的这样的数都有哪些。但是写着写着机智的Tabris发现这样神奇的数实在太多了，所以向你求助，你能帮帮他们吗？
测试样例
无
解题思路
实际上很好想，毕竟已经固定了数的长度大小，并且还要保证字符对称，所以我们只需要枚举前4位即可，再使用字符串翻转即可实现。
解题代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
//一定要注意首位不可以是0但是其他位都是可以从0开始的
for (int i = 1000; i <= 9999; i++)
//前四位翻转即为后四位
{
string str = "";
int t = i;
while (t != 0)
{
//强制转换后，拼接
str = char(t % 10 + '0') + str + char(t % 10 + '0');
//除10取下一位
t /= 10;
}
cout << str << endl;
}
system("pause");
return 0;
} PTA1327634546768367617-大采购
题目链接
https://pintia.cn/problem-sets/1327634511926284288/problems/1327634546768367617
题目描述
众所周知，龙龙十分喜欢逛中关村南门出去几百米远的那个五星超市。这天龙龙拉着yds一起去逛五星超市，龙龙推着一个重量上限为N的购物车。他们在五星超市中逛了一圈也没看见什么想买的，购物车里还是空的，这时龙龙突然发现后门附近还有一条长长的货物架，上面有M个商品，每个商品分别有重量G，和价值S两个属性，但这个购物架是单向的，也就是说龙龙只能从现在所处的这端走到另一端将商品按顺序放入购物车中。龙龙说他可以轻松的将一些商品放入放入购物车中使得在购物车的重量承受范围内，商品的总价值最大。但yds心想，这不就是一个简单的01背包问题？恶毒的yds并不想让龙龙简单的解决这个问题，他要求龙龙在只能按顺序放入商品之外，每次放入的商品的重量还必须小于等于上一次放入的商品的重量。龙龙觉得这个问题就有点费脑筋了，他并不想去仔细思考，请你帮他算出他在这样的规则下最多能往购物车里塞价值为多少的商品。
第一行输入两个整数N，M，分别代表购物车的重量限制与商品的个，(1≤N≤100,1≤M≤100)。接下来M行，每行输入两个整数Gi,Si，分别代表第i个商品的重量与价值，(1≤Gi,Si≤100)。
测试样例
输入
5 5 1 5 2 2 3 3 4 4 1 2
输出
7
解题思路
这道题实际上是一个0/1背包dp的三维打表，可以参考《0/1dp从二维升为三维的问题》。这里我们使用三维dp打表，f[i][j][k]的前两个i,j意义不变表示的是背包剩余容量为j时，从物品1~i选择可获得的最大收益值。而k就是表示上一个所选择的最大物品质量，所以此时f函数的意义就变成了f[i][j][k]的前两个i,j意义不变表示的是背包剩余容量为j时，从物品1~i选择同时保证上一个被选择的物品质量是k时可获得的最大收益值。那么每一次我们都要求当前选择的物品质量w[i]<k即可。同时还要注意memset函数的赋值，此处的255实际上赋值后全为-1。
解题代码
解法一：三维打表
#include <bits/stdc++.h>
using namespace std;
#define close_stdin ios::sync_with_stdio(false)
const int N = 1e2;
int dp[N + 5][N + 5][N + 5], w[N + 5], v[N + 5];
int main()
{
close_stdin;
int ans = 0;
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> w[i] >> v[i];
}
//初始化为-1
memset(dp, 255, sizeof(dp));
for (int i = 0; i <= n; i++)
{
//将i=0的情况全部设定为0，因为无法选物品当然就是0了
dp[0][0][i] = 0;
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= n; k++)
{
//此时要三层嵌套，枚举k
//当为-1时，表示上一个表格未满足条件不能赋值，所以跳过以防影响后面的打表
if (!~dp[i][j][k])
continue;
//满足条件时先将这个格的下一个格赋值为当前格的值，表示不放入物品i+1的收益情况就是此时i的情况
dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
//当满足w[i]<K时我们利用递归式求解放入和不放入的情况哪个收益更好
if (w[i + 1] <= k && j + w[i] <= n)
{
dp[i + 1][j + w[i + 1]][w[i + 1]] = max(dp[i + 1][j + w[i + 1]][w[i + 1]], dp[i][j][k] + v[i + 1]);
}
}
}
}
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= n; k++)
{
//选取最好收益情况，此时j未必等于N且k也未必是w[n]
ans = max(ans, dp[m][j][k]);
}
}
cout << ans << endl;
system("pause");
return 0;
} 解法二：降为二维dp打表
实际上此题也可以降维，我们知道在二维0/1dp降维时是使j从N到0，同时每一次进行递归的条件是满足j>=w[i]才可以，这道题我们参照这个思路，同样降维，只是在j>=w[i]的同时还需要满足k<=j。所以需要二维dp,数组的后一个参数就是k记录上一次的被选择物品质量，同样，我们降维降得是不需要i，所以仍然是多次覆盖数据，没有参数i。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 110;
int v[maxn], w[maxn], dp[maxn][maxn]; //记录上一个物品的重量
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
int n, m;
while (cin >> n >> m)
{ //n容量m物品
memset(dp, 0, sizeof dp);
for (int i = 0; i < m; ++i)
cin >> w[i] >> v[i];
int ans = 0; //记录答案
for (int i = 0; i < m; ++i)
{ //到第i件物品
for (int j = n; j >= w[i]; --j)
{ //优化降维,逆序由上一轮到本轮,总共选了j重量
for (int k = w[i]; k <= j; ++k)
{ //最后一个物品重量为k,保证递减
dp[j][w[i]] = max(dp[j][w[i]], dp[j - w[i]][k] + v[i]); //
}
ans = max(ans, dp[j][w[i]]);
}
}
cout << ans << endl;
}
//system("pause");
return 0;
} 
投递网易有道等公司6个岗位 >