DPのfor a week

P1734最大约数和

选取和不超过 $S$ 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大
如取数字 $4$ 和 $6$ ，可以得到最大值 $(1 + 2) + (1 + 2 + 3) = 9$ 。

#include <iostream>
#include <vector>
using namespace std;int a(int x) {vector<int> a(x + 1, 0);for (int i = 1; i <= x; ++i) {for (int j = 2 * i; j <= x; j += i) {a[j] += i;}}vector<int> dp(x + 1, 0);for (int i = 1; i <= x; ++i) {for (int j = 1; j <= i; ++j) {dp[i] = max(dp[i], dp[i - j] + a[j]);}}return dp[x];
}int main() {int x;cin >> x;cout << a(x) << endl; return 0;
}

AT_arc148_b [ARC148B]
将字符串翻转，然后把所有 d 换成 p，把所有 p 换成 d。

#include<bits/stdc++.h>
using namespace std;int main(){
int n,m=-1;
string a,b,c;cin>>n>>a;for(int i=0;i<=n-1;i++){if(a[i]=='p'){m=i;break;}}if(m==-1){cout<<a;}else{c.push_back('z');for(int i =m;i <= n-1; i++){b=a;for(int j = m;j <= i;j++){if(b[j]=='d'){b[j]='p';}else{b[j]='d';}}for(int j = m;2*j <= i+m; j++){swap(b[j],b[i-j+m]);}c=min(c,b);}}cout<<c;return 0;
}

P2430严酷的训练

题目背景

Lj 的朋友 WKY 是一名神奇的少年，在同龄人之中有着极高的地位。。。

题目描述

他的老师老王对他的程序水平赞叹不已，于是下决心培养这名小子。

老王的训练方式很奇怪，他会一口气让 WKY 做很多道题，要求他在规定的时间完成。而老王为了让自己的威信提高，自己也会把这些题都做一遍。

WKY 和老王都有一个水平值，他们水平值的比值和做这些题所用时间的比值成反比。比如如果 WKY 的水平值是 $1$ ，老王的水平值是 $2$ ，那么 WKY 做同一道题的时间就是老王的 $2$ 倍。

每个题目有他所属的知识点，这我们都知道，比如递归，动规，最短路，网络流。在这里我们不考虑这些事情，我们只知道他们分别是知识点 $1$ ，知识点 $2$ ……每一个知识点有他对应的难度，比如动态规划经常难于模拟。

而每一个同一知识点下的题目，对于 WKY 来讲，都是一样难的。而做出每一道题，老王都有其独特的奖励值。而奖励值和题目的知识点没有必然联系。

现在 WKY 同学请你帮忙，计算在老王规定的时间内，WKY 所能得到最大奖励值是多少。

变态の采药

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int lw, wky; int m, n;   vector<int> z(5010, 0); // 老王时间vector<int> p(5010, 0); // 知识点编号vector<int> q(5010, 0); // 价值vector<int> f(5010, 0); //j内的最大价值cin >> wky >> lw;lw = lw / wky; // wky做一题的时间是老王的多少倍cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> z[i];z[i] = z[i] * lw; }for (int i = 1; i <= m; i++) {cin >> p[i] >> q[i];p[i] = z[p[i]]; // wky做这道题要用的时间}for (int i = 1; i <= m; i++) {for (int j = n; j >= p[i]; j--) {f[j] = max(f[j], f[j - p[i]] + q[i]);}}// 输出结果cout << f[n] << endl;return 0;
}

珈百璃堕落的开始

题目描述

这道题是这样的：给定一些 $sin^2x$ ， $\cos^2x\ \left(x=\dfrac{\pi}{7}\right)$ 组成的式子，请你帮忙求出选择一些式子相加后得到的最大整数答案。

输入格式

第一行一个整数 $n$ ，表示 $n$ 个式子

接下来 $n$ 行每行一个字符串，由 $f(i)=\sin^2x,\cos^2x$ 和加号组成， $x=\dfrac{\pi}{7}$ 。

为了简化输入，我们以 s 代表 $sin^2x$ ，以 c 代表 $cos^2x$ ，并省略 f(i)=。

不会二维，偏移量处理负索引不怎么明白，dp学完再来

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;const int D = 1e6 + 90; // 偏移量，用于处理负索引int main() {int n;cin >> n;vector<int> f(2 * D, -1e9);vector<int> g(2 * D, -1e9);g[D] = 0; // 初始状态的最大价值int l = 0, r = 0; // l表示至今最小重量，r表示最大重量for (int i = 1; i <= n; i++) {string a;cin >> a;int sums = 0, sumc = 0;for (char c : a) {if (c == 's') sums++;else if (c == 'c') sumc++;}int v = sums, w = sums - sumc;l = min(l, l + w);r = max(r, r + w);for (int j = l + D; j <= r + D; j++) {f[j] = max(f[j], max(g[j], g[j - w] + v));}for (int j = l + D; j <= r + D; j++) {g[j] = f[j];}}cout << f[D] << endl;return 0;
}