#algorithm/动态规划
01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0 < N, V ≤ 1000
0 < vi, wi ≤ 1000
|
输入样例
输出样例：
Source Code
#include <iostream>
#include <vector>
#include <string>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
const int M = 1e3 + 10;
int n, m, t;
int v[M], w[M];
int f[M][M];
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
f[i][j] = f[i - 1][j];
if(j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << '\n';
}
signed main()
{
IOS;
int T = 1;
while(T--)solve();
return 0;
}
|
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1e6 + 10;
const int N = 1e3 + 10;
int n, m;
int main(){
cin >> n >> m;
int wt[N], val[N];
int dp[N][N];
for(int i = 0; i < N; i++){
cin >> wt[i] >> val[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(j - wt[i - 1] < 0){
dp[i][j] = dp[i - 1][j];
}else {
dp[i][j] = max(
dp[i - 1][j - wt[i - 1]] + val[i - 1],
dp[i - 1][j]
);
}
}
}
cout << dp[n][m];
}
|
#include <iostream>
#include <vector>
#include <string>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
const int M = 1e3 + 10;
int n, m, t;
int v[M], w[M];
int f[M];
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << '\n';
}
signed main()
{
IOS;
int T = 1;
while(T--)solve();
return 0;
}
|
翻硬币
题目描述
小明正在玩一个”翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。 比如，可能情形是：oooooo; 如果同时翻转左边的两个硬币，则变为：oooo**oooo。 现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？ 我们约定：把翻动相邻的两个硬币叫做一步操作。
输入描述
两行等长的字符串，分别表示初始状态和要达到的目标状态。 每行的长度<1000。
输出描述
一个整数，表示最小操作步数。
输入输出样例
示例
输入
输出
Source Code
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
const int M = 1e3 + 10;
int n, m, t;
string s1, s;
void check(int i){
if(s[i] == '*')s[i] = 'o';
else s[i] = '*';
}
void solve() {
getline(cin, s);
getline(cin, s1);
int sum = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] != s1[i]){
check(i);
check(i + 1);
sum ++;
}
}
cout << sum;
}
signed main()
{
IOS;
int T = 1;
while(T--)solve();
return 0;
}
|
题目描述
给定一个单词，请问在单词中删除 t 个字母后，能得到的字典序最小的单词是什么？
输入描述
输入的第一行包含一个单词，由大写英文字母组成。 第二行包含一个正整数 t_。 其中，单词长度不超过 100，_t 小于单词长度。
输出描述
输出一个单词，表示答案。
输入输出样例
示例 1
输入
输出
Source Code
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
getline(cin, s);
int size;
cin >> size;
int ch[s.length()], arr[s.length() - size];
int count = 0, a = 0, flag = a;
for (int i = 0; i < s.length(); i++) {
ch[i] = s[i] - 'A';
}
while (size > 0) {
flag = a;
for (int i = a; i <= flag + size; i++) {
if (ch[a] > ch[i]) {
a = i;
}
}
size -= (a - flag);
arr[count++] = ch[a];
a++;
}
for (int i = a; i < s.length(); i++) {
arr[count++] = ch[i];
}
for (int i = 0; i < count; i++) {
cout << (char)(arr[i] + 'A');
}
return 0;
}
|
2834. 找出美丽数组的最小和
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
nums.length == n.nums 由两两互不相同的正整数组成。- 在范围
[0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。
返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 109 + 7。
示例 1：
输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。
|
示例 2：
输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。
- nums 的长度为 n = 3 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。
|
示例 3：
**输入：**n = 1, target = 1
**输出：**1
**解释：**nums = [1] 是美丽数组。
|
提示：
1 <= n <= 1091 <= target <= 109