笔试强训Day18 字符串 排序 动态规划

本文主要是介绍笔试强训Day18 字符串 排序 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[编程题]压缩字符串(一)

题目链接：压缩字符串(一)__牛客网 (nowcoder.com)

思路：

跟着思路写就完了。

AC code：

#include <iostream>
#include<string>
using namespace std;
string a;
string ans;
int main()
{cin >> a;int j = 0;for(int i = 0; i < a.size(); i ++){int cnt = 0;for(j = i; j < a.size(); j ++){if(a[j] == a[i])cnt++;else break;}if(cnt > 1)ans += a[i] + to_string(cnt);else ans += a[i];i = j - 1;}cout << ans << endl;return 0;
}

chika和蜜柑

题目链接：chika和蜜柑 (nowcoder.com)

思路：

简单的排序问题。

AC code：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;const int N = 2e5 + 10;
PII a[N];
int n,m;
long long ans1,ans2;bool cmp(PII x, PII y)
{if(x.first == y.first) return x.second < y.second;return x.first > y.first;
}int main()
{cin >> n >> m;for(int i = 0; i < n; i ++)cin >> a[i].second;for (int i = 0; i < n; i ++ )cin >> a[i].first;sort(a, a + n, cmp);    for(int i = 0; i < m; i ++){ans1 += a[i].first;ans2 += a[i].second;}cout << ans2 << ' ' << ans1;return 0;
}

NC145 01背包

题目链接：01背包_牛客题霸_牛客网 (nowcoder.com)

思路：

经典01背包一维优化 注意本题 i + 1 代表了 第 i 个 物品的属性。

AC code：

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 计算01背包问题的结果* @param V int整型 背包的体积* @param n int整型 物品的个数* @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi* @return int整型*/int knapsack(int V, int n, vector<vector<int> >& vw){vector<int>f(V + 10);for(int i = 1; i <= n; i ++)for(int j = V; j >= vw[i - 1][0]; j --)f[j] = max(f[j], f[j - vw[i - 1][0]] + vw[i - 1][1]);return f[V];}
};

这篇关于笔试强训Day18 字符串 排序 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---