题目描述
复习与回顾
版权所有 Peppa_Even_Pig(AGP) 正版标识,侵权必究!
C++ 代码
一、模板;
0xff、快读快写(__int128适用);
#include <iostream>
using namespace std;
typedef __int128 LLL;
LLL read() {
LLL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void out(LLL x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
int n;
int main() {
cin >> n;
__int128 a, b;
char c;
for (int i = 1; i <= n; i++) {
a = read();
cin >> c;
b = read();
if (c == '+') {
out(a + b);
cout << endl;
}
if (c == '-') {
out(a - b);
cout << endl;
}
}
return 0;
}
0x7f、筛法求素数;
埃氏筛;O(n log log n);
#include <iostream>
#include <cstring>
using namespace std;
int n;
int vis[100000005];
int main() {
cin >> n;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
if (vis[i]) continue;
cout << i << endl;
for (int j = i; j <= n / i; j++) vis[i * j] = 1;
}
return 0;
}
线性筛 O(n);
#include <iostream>
#include <cstring>
using namespace std;
int n;
int vis[100000005];
int p[100000005];
int main() {
cin >> n;
memset(vis, 0, sizeof(vis));
int m = 0;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
vis[i] = i;
p[++m] = i;
}
for (int j = 1; j <= m; j++) {
if (p[j] > vis[i] || p[j] > n / i) break;
vis[i * p[j]] = p[j];
}
}
for (int i = 1; i <= m; i++) cout << p[i] << endl;
return 0;
}
1、高精度;
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
char a[10005], b[10005];
int a1[10005], b1[10005], c[10005];
int lena, lenb, lenc;
int x; //进位;
void gao_jing_jia(int a1[], int b1[]) {
memset(c, 0, sizeof(c));
lenc = max(lena, lenb);
x = 0;
for (int i = 0; i <= lenc - 1; i++) {
c[i] = a1[i] + b1[i] + x;
x = c[i] / 10;
c[i] %= 10;
}
if (x) {
lenc++;
c[lenc - 1] = x;
}
}
void gao_jing_jian(int a1[], int b1[]) {
memset(c, 0, sizeof(c));
lenc = max(lena, lenb);
x = 0;
if ((lena < lenb) || ((lena == lenb) && a1[lena - 1] < b1[lenb - 1])) {
cout << '-';
for (int i = 0; i <= lenc - 1; i++) {
if (b1[i] - a1[i] < 0) {
b1[i + 1]--;
b1[i] += 10;
}
c[i] = b1[i] - a1[i];
}
while(!c[lenc - 1]) {
if (lenc - 1 == 0) break;
lenc--;
}
} else {
for (int i = 0; i <= lenc - 1; i++) {
if (a1[i] - b1[i] < 0) {
a1[i + 1]--;
a1[i] += 10;
}
c[i] = a1[i] - b1[i];
}
while(!c[lenc - 1]) {
if (lenc - 1 == 0) break;
lenc--;
}
}
}
void gao_jing_cheng(int a1[], int b1[]) {
if (((lena == 1) && a1[0] == 0) || ((lenb == 1) && b1[0] == 0)) {
c[0] = 0;
lenc = 1;
return;
}
lenc = lena + lenb;
for (int i = 0; i <= lena - 1; i++) {
for (int j = 0; j <= lenb - 1; j++) {
c[i + j] += a1[i] * b1[j];
c[i + j + 1] += c[i + j] / 10;
c[i + j] %= 10;
}
}
while(!c[lenc - 1]) lenc--;
}
int main() {
cin >> a >> b;
lena = strlen(a);
lenb = strlen(b);
for (int i = 0; i < lena; i++) { //倒着存,方便进位;
a1[i] = a[lena - i - 1] - '0';
}
for (int i = 0; i < lenb; i++) {
b1[i] = b[lenb - i - 1] - '0';
}
// gao_jing_jia(a1, b1);
// gao_jing_jian(a1, b1);
// gao_jing_cheng(a1, b1);
for (int i = lenc - 1; i >= 0; i--) {
cout << c[i];
}
return 0;
}
//2、归并排序与逆序对;
#include <iostream>
#include <cstdio>
using namespace std;
int a[5000005]; //待排序数组;
int r1[5000005]; //排好序数组;
int n;
long long ans; //注意long long;
void merge_sort(int l, int r) {
if (l == r) return;
int m = (l + r) >> 1;
int i, j, k;
merge_sort(l, m);
merge_sort(m + 1, r);
i = l;
k = l;
j = m + 1;
while(i <= m && j <= r) {
if (a[i] <= a[j]) {
r1[k] = a[i]; //r[k]每次都存较小的那一个;
k++;
i++;
}
if (a[i] > a[j]) {
r1[k] = a[j];
k++;
j++;
ans += m - i + 1; //逆序对个数,因为r数组已部分排好序(从中点出发),所以m - i + 1就是逆序对个数;
}
}
while(i <= m) { //将左边剩余元素接入r数组中;
r1[k] = a[i];
i++;
k++;
}
while(j <= r) { //将右边剩余元素接入r数组中;
r1[k] = a[j];
j++;
k++;
}
for (int i = l; i <= r; i++) {
a[i] = r1[i]; //将a数组排为有序;
}
}
int main() {
scanf("%d", &n); //不要用cin,否则可能会超时;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
merge_sort(1, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
printf("\n");
printf("%lld", ans);
return 0;
}
//3、二分查找与二分答案;
#include <iostream>
using namespace std;
int a[10005];
int n;
int l, r;
int y;
bool check(int x) {
if (a[x] >= y) return true;
else return false;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> y; //待查找元素;
l = 1;
r = n;
while(l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (a[l] != y) {
cout << "No Answer!";
return 0;
}
cout << l;
return 0;
}
//4、快速幂取模;
//输出 a ^ b % c 的值;
#include <iostream>
using namespace std;
long long a, b, c;
long long kuai_su_mi(long long a, long long b, long long c) {
long long ans = 1;
while (b > 0) {
if (b & 1) {
ans = (ans * a) % c;
}
a = a * a % c;
b >>= 1;
}
return ans;
}
int main() {
cin >> a >> b >> c;
cout << kuai_su_mi(a, b, c);
return 0;
}
5、图论模板;
<1> 树;
A、二叉树的前,中,后序遍历;
#include <iostream>
using namespace std;
int n;
struct sss{ //树的存储;
char v;
int ls, rs; //节点值,左孩子(编号),右孩子(编号);
}tr[100005];
void xian(int x) { //根左右;
if (x != 0) {
cout << tr[x].v;
xian(tr[x].ls);
xian(tr[x].rs);
}
}
void zhong(int x) { //左根右;
if (x != 0) {
zhong(tr[x].ls);
cout << tr[x].v;
zhong(tr[x].rs);
}
}
void hou(int x) { //左右根;
if (x != 0) {
hou(tr[x].ls);
hou(tr[x].rs);
cout << tr[x].v;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> tr[i].v;
cin >> tr[i].ls >> tr[i].rs;
}
xian(1);
cout << endl;
zhong(1);
cout << endl;
hou(1);
cout << endl;
return 0;
}
B、普通树转二叉树;
#include <iostream>
using namespace std;
int n;
struct sss{
char a;
int ls, rs;
}e[100005];
void qian(int x) {
if (x) {
cout << e[x].a;
qian(e[x].ls);
qian(e[x].rs);
}
}
void hou(int x) {
if (x) {
hou(e[x].ls);
hou(e[x].rs);
cout << e[x].a;
}
}
int main() {
cin >> n;
int o = 1;
int b;
int p;
for (int i = 1; i <= n; i++) {
cin >> e[i].a;
cin >> b;
if (b != 0) {
e[i].ls = b; //将与根节点链接的第一个节点作为此节点的左孩子;
}
p = b;
while (b != 0) {
cin >> b;
if (b != 0) { //有可能b == 0,所以要特判;
e[p].rs = b; //加边,原来的兄弟变为右孩子; (同时也删了边(兄弟和根节点的边));
}
p = b;
}
}
qian(1);
cout << endl;
hou(1);
return 0;
} //最后旋转处理(在纸上)就可得到一个二叉树;
C、已知中后求前;
#include <iostream>
#include <string>
using namespace std;
string a, b;
void zhong_hou_qiou_qian(string x, string y) {
int xl = x.size(), yl = y.size();
cout << y[yl - 1];
if (yl == 1) return; //只有根节点;
int k = x.find(y[yl - 1], 0);
if (k > 0) {
string s1 = x.substr(0, k);
string s2 = y.substr(0, k);
zhong_hou_qiou_qian(s1, s2);
}
if (k < yl - 1) {
string s3 = x.substr(k + 1, xl - k - 1);
string s4 = y.substr(yl - s3.size() - 1, s3.size());
zhong_hou_qiou_qian(s3, s4);
}
}
int main() {
cin >> a >> b;
zhong_hou_qiou_qian(a, b);
return 0;
}
D、已知前中求后;
#include <iostream>
#include <string>
using namespace std;
string a, b;
int s;
void qian_zhong_qiou_hou(int l, int r) {
if (l > r) return; //当l == r时还能再找根(下标为l);不能写l >= r;
for (int i = l; i <= r; i++) {
if (a[s] == b[i]) { //如果在b中找到根;
s++; //更新根;
qian_zhong_qiou_hou(l, i - 1);
qian_zhong_qiou_hou(i + 1, r); //递归时不能再有此根;
cout << b[i]; //左右根;
}
}
}
int main() {
cin >> a >> b;
s = 0;
qian_zhong_qiou_hou(0, a.size() - 1);
return 0;
}
注:已知前后不能求中,因为树不是唯一确定的;
E、二叉排序树(中序遍历有序);
左子树的所有节点比此节点小,右子树的所有节点比此节点大;
板子(无注释):
#include <iostream>
using namespace std;
struct sss{
int a;
int ls, rs;
}e[1000005];
int n;
void zhong(int x) {
if (x) {
zhong(e[x].ls);
cout << e[x].a << ' ';
zhong(e[x].rs);
}
}
void hou(int x) {
if (x) {
hou(e[x].ls);
hou(e[x].rs);
cout << e[x].a << ' ';
}
}
int main() {
cin >> n;
int x = 0;
int p = 0;
for (int i = 1; i <= n; i++) {
cin >> e[i].a;
x = e[i].a;
if (i == 1) continue;
p = 1;
while(1) {
if (x < e[p].a) {
if (e[p].ls != 0) {
p = e[p].ls;
continue;
} else {
e[p].ls = i;
break;
}
} else {
if (e[p].rs != 0) {
p = e[p].rs;
continue;
} else {
e[p].rs = i;
break;
}
}
}
}
zhong(1);
cout << endl;
hou(1);
return 0;
}
F、最优二叉树(哈夫曼树 Huffman Tree);
带权路径长度之和达到最小的二叉树;
板子(无注释):
#include <iostream>
using namespace std;
long long n;
struct sss{
long long a;
long long ls, rs;
}e[100005];
sss eg[100005];
int k;
long long ma() {
long long t = -1;
for (int i = 1; i <= n; i++) {
if (e[i].a > t) {
t = e[i].a;
k = i;
}
}
e[k].a = -1;
return t;
}
long long mi() {
long long t = 0xfffffffffffff;
for (int i = 1; i <= n; i++) {
if (eg[i].a < t) {
t = eg[i].a;
k = i;
}
}
eg[k].a = 0xfffffffffff;
return t;
}
void ma_t() {
for (int i = n + 1; i <= 2 * n - 1; i++) {
e[i].ls = ma();
e[i].rs = ma();
e[i].a = e[i].ls * e[i].rs + 1;
e[k].a = e[i].a;
}
}
void mi_t() {
for (int i = n + 1; i <= 2 * n - 1; i++) {
eg[i].ls = mi();
eg[i].rs = mi();
eg[i].a = eg[i].ls * eg[i].rs + 1;
eg[k].a = eg[i].a;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> e[i].a;
eg[i].a = e[i].a;
}
mi_t();
ma_t();
cout << eg[2 * n - 1].a << endl;
cout << e[2 * n - 1].a << endl;
cout << eg[2 * n - 1].a - e[2 * n - 1].a;
return 0;
}
<2> 图的最短路(注意初始化);
A、图的存储;
1. 邻接矩阵;
#include <iostream>
using namespace std;
int n;
int a[1005][1005];
int main() {
cin >> n;
int x, y, w; //起点,终点,权值;
for (int i = 1; i <= n; i++) {
cin >> x >> y >> w;
a[x][y] = w;
a[y][x] = w; //双向边,若有向图则不用加;
}
return 0;
}
2. 链式前向星;
#include <iostream>
using namespace std;
int n;
struct sss{
int t, ne, w;
}e[100005];
int h[100005], cnt;
void add(int u, int v, int ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
e[cnt].w = ww;
h[u] = cnt;
}
int main() {
cin >> n;
int x, y, w; //起点,终点,权值;
for (int i = 1; i <= n; i++) {
cin >> x >> y >> w;
add(x, y, w);
add(y, x, w); //双向边,若有向图则不用加;
}
for (int i = 1; i <= n; i++) {
cout << i << "连接的点";
for (int j = h[i]; j; j = e[j].ne) {
cout << e[j].t << ' ';
}
cout << endl;
} //遍历;
return 0;
}
3. 弗洛伊德(Floyd);
DP的思想,O(n^3)的做法;
多源最短路;
模板(邻接矩阵):
#include <iostream>
#include <cstring>
using namespace std;
int n, m; //n个点,m条边;
int a[1005][1005];
int main() {
cin >> n >> m;
memset(a, 0x3f, sizeof(a)); //后面要找min,所以初始化很大;
int x, y, w;
for (int i = 1; i <= n; i++) a[i][i] = 0;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
a[x][y] = a[y][x] = w;
}
for (int k = 1; k <= n; k++) { //先枚举中间点;
for (int i = 1; j <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
Floyd求最小环;
#include <iostream>
#include <cstring>
using namespace std;
int n, m; //n个点,m条边;
int a[1005][1005];
int dis[1005][1005];
int main() {
cin >> n >> m;
memset(dis, 0x3f, sizeof(dis)); //后面要找min,所以初始化很大;
int x, y, w;
for (int i = 1; i <= n; i++) a[i][i] = 0;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
a[x][y] = a[y][x] = w;
dis[x][y] = dis[y][x] = w;
}
int ans = 0xfffffffffff;
for (int k = 1; k <= n; k++) { //先枚举中间点;
for (int i = 1; i <= k - 1; i++) {
for (int j = i; j <= k - 1; j++) {
ans = min(ans, dis[i][j] + a[j][k] + a[k][i]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
cout << ans; //最小环长度;
return 0;
}
4. Dijstra;
每次松弛一个点,一共松弛n次;
朴素 O(n^2) 模板(邻接矩阵);
#include <iostream>
#include <cstring>
using namespace std;
int n, m; //点数,边数;
int dis[100005];
bool vis[100005];
int a[1005][1005];
void Dijstra(int x) { //x为起点;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x] = 0;
int t = -1;
for (int i = 2; i <= n; i++) { //除去起点,只需松弛n - 1次;
for (int j = 1; j <= n; j++) {
if (!vis[x] && (t == -1 || dis[j] < dis[t])) t = j; //找到离源点最近的最优点;
}
vis[t] = true;
for (int j = 1; j <= n; j++) {
if (dis[j] < dis[t] + a[t][j]) {
dis[j] = dis[t] + a[t][j];
}
}
}
if (dis[m] == 0x3f3f3f3f) {
cout << -1;
} else cout << dis[m];
}
int main() {
cin >> n >> m;
int x, y, w;
for (int i = 1; i <= n; i++) {
cin >> x >> y >> w;
a[x][y] = w;
a[y][x] = w;
}
Dijstra(1);
return 0;
}
堆优化 (O(n log n));
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, m; //点数,边数;
struct sss {
int t, ne, w;
}e[100005];
int h[100005], cnt;
void add(int u, int v, int ww) {
e[++cnt].w = ww;
e[cnt].ne = h[u];
e[cnt].t = v;
h[u] = cnt;
}
typedef pair<int, int> P;
void Dijstra_dui_you_hua(int x) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x] = 0;
priority_queue<P, vector<P>, greater<P> > q; //权值在前,序号在后,队列里存的是已经松驰过的;
q.push({0, x});
while(!q.empty()) {
int t = q.top().first;
int xu = q.top().second;
q.pop();
if (vis[xu]) continue;
vis[xu] = true;
for (int i = h[xu]; i; i = e[i].ne) {
int u = e[i].t;
if (dis[u] > dis[xu] + e[i].w) {
dis[u] = dis[xu] + e[i].w;
q.push({dis[u], u});
}
}
}
if (dis[m] == 0x3f3f3f3f) cout << -1;
else cout << dis[m];
}
int main() {
cin >> n >> m;
int x, y, w;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
add(x, y, w);
add(y, x, w);
}
Dijstra_dui_you_hua(1);
return 0;
}
5. Bellman_Ford 以及 SPFA;
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, m;
struct sss{
int t, ne, w;
}e[100005];
int h[100005], cnt;
void add(int u, int v, int ww) {
e[++cnt].t = v;
e[cnt].w = ww;
e[cnt].ne = h[u];
h[u] = cnt;
}
int dis[100005];
bool vis[100005];
void SPFA(int x) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x] = 0;
vis[x] = true;
queue<int> q;
q.push(x);
while(!q.empty()) {
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i; i = e[i].ne) {
int u = e[i].t;
if (dis[u] > dis[t] + e[i].w) {
dis[u] = dis[t] + e[i].w;
if (!vis[u]) {
q.push(u);
vis[u] = true;
}
}
}
}
}
int backup[1005];
int Bellman_Ford(int x, int k, int m) { //k为到点n的最多经过的边数,m为总边数。正确性待检验;
memset(dis, 0x3f, sizeof(dis));
dis[x] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, dis, sizeof(dis)); //备份,防止串联。
for (int j = 1; j <= m; j++) {
int a = e[j].f, b = e[j].t, ww = e[j].w;
dis[b] = min(dis[b], backup[a] + e[j].w);
}
}
if (dis[n] < 0x3f3f3f3f / 2) {
return dis[n];
} else return -1;
}
int main() {
cin >> n >> m;
int x, y, w;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
add(x, y, w);
add(y, x, w);
}
Bellman_Ford(1);
return 0;
}
SPFA判负环;
因为SFPA的本质是Bellman-Ford的队列优化,其记录的是从源点到此点最多经过k条边的最短路,所以如果经过n-1次后还能更新,说明图中存在负环;
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int f;
struct sss{
int t, w, ne;
}e[100005];
int h[100005], cnt;
void add(int u, int v, int ww) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
e[cnt].w = ww;
}
int dis[100005];
bool vis[100005];
int n, m, w;
int cn[100005]; //c[i]代表第i个点到源点所需边数;
bool SPFA(int x, int n) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(cn, 0, sizeof(cn));
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i);
vis[i] = true;
}
while(!q.empty()) {
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != 0; i = e[i].ne) {
int to = e[i].t;
if (dis[to] > dis[t] + e[i].w) {
dis[to] = dis[t] + e[i].w;
cn[to] = cn[t] + 1;
if (cn[to] >= n) return true; //满足条件,直接return;
if (!vis[to]) {
q.push(to);
vis[to] = true;
}
}
}
}
return false;
}
int main() {
cin >> f;
for (int i = 1; i <= f; i++) {
cin >> n >> m >> w;
memset(h, 0, sizeof(h));
for (int j = 1; j <= n; j++) {
e[j].ne = 0;
e[j].t = 0;
e[j].w = 0;
}
cnt = 0;
int u, v, ww;
for (int j = 1; j <= m; j++) {
cin >> u >> v >> ww;
add(u, v, ww);
add(v, u, ww);
}
for (int j = 1; j <= w; j++) {
cin >> u >> v >> ww;
add(u, v, -ww);
}
if (SPFA(1, n)) {
cout << "YES" << endl; //有负环;
} else {
cout << "NO" << endl; //无负环;
}
}
return 0;
}
6. 并查集(略);
二、玄学DP;(初始化很重要);
大前提:1、最优子结构;2、无后效性(不被前面影响);
要点:1、初始化;2、状态转移方程;(重点);
1、记忆化搜索;
其实,记忆化搜索就是递归版的DP,其用数组记录符合下标条件的(最优)价值;
但符合记忆化搜索需要满足搜索树在下方的某(几)个节点交汇,否则记忆化就变成了DFS,还会增加空间复杂度;
例题:杨辉三角:
1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
记忆化:if (!memory[n][m]) memory[n][m] = f(n - 1, m) + f(n, m - 1);
return memory[n][m];
递归边界条件:if (n == m) return 1;
if (n == 0) return 0;
if (m == 0) return n;
2、背包DP;
<1> 01背包: 01背包本质是由上层状态转移而来(满足条件的前提),由于其只能选一次,状态的转移沿对角线方向;初始化为题目所要求;(一般为f[0][0] = 0; memset(f, 0, sizeof(f)););
当某一层状态转移满时,其后的状态可能会出现不可预料的错误(一般是由于初始化导致的)(初始化非常重要!!!)(其实最优解就在最后一行的某个地方);当初始化为0xcf时, 可能会出现f[][]数组中有0xcf+符合条件的最优价值的情况;cout << f[n][m]; 也无法出现最优解;(其实f数组中可能根本没有最优解,(初始化已经出现错误,体现了初始化的重要性),max也没用);
模板:
(滚动数组)
#include <iostream>
#include <cstring>
using namespace std;
int c[10005], w[10005]; //w[i]为第i件物品的重量,c[i]为第i件物品的价值;
int f[10005]; //f[i]为 容量为i时的最大价值;
int m, n; //m为背包容量,n为总物品数量;
int main() {
cin >> m >> n;
memset(f, 0, sizeof(f)); //初始化,等待赋值;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i];
}
f[0] = 0; //初始化,当容量为0时最大价值为0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + c[i]);
}
}
cout << f[m];
return 0;
}
(朴素)
#include <iostream>
#include <cstring>
using namespace std;
int f[2005][2005]; //f[i][j]表示前i件物品,容量为j时最大价值;
int m, n;
int w[10005], c[10005];
int main() {
cin >> m >> n;
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i];
}
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
}
for (int j = w[i]; j <= m; j++) {
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + c[i]);
}
}
cout << f[n][m];
return 0;
}
为啥内层循环要倒序呢?因为每种物品只能选一次, 其实就是第i层的状态只能由第i-1层的状态转移一次得来,若顺序,则当第i层第j个状态被更新时,它就到了第i-1层,后面的第i层的j + w[i]个状态又可能被此状态更新,这样一个物品就拿了两次;
如此循环往复,则物品都能哪无限次了;
so,引出下一个背包——
<2> 完全背包(能拿无限件);
顺序就完事了;
#include <iostream>
#include <cstring>
using namespace std;
int c[1000005], w[1000005]; //w[i]为第i件物品的重量,c[i]为第i件物品的价值;
int f[1000005]; //f[i]为 容量为i时的最大价值;
int m, n; //m为背包容量,n为总物品数量;
int main() {
cin >> m >> n;
memset(f, 0, sizeof(f)); //初始化,等待赋值;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i];
}
f[0] = 0; //初始化,当容量为0时最大价值为0;
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
f[j] = max(f[j], f[j - w[i]] + c[i]);
}
}
cout << f[m];
return 0;
}
<3> 多重背包(一个物品只能取有限次);
其实多重背包可以看作是01背包和完全背包的结合版,只需将其转化成01背包,枚举次数求解即可;
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
int w[100005], c[100005], num[100005]; //重量,价值,个数;
int f[100005];
int main() {
cin >> n >> m;
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i] >> num[i];
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
for (int k = 1; k <= num[i] && k * w[i] <= j; k++) { //枚举个数;
f[j] = max(f[j], f[j - k * w[i]] + k * c[i]);
}
}
}
cout << f[m];
return 0;
}
但是,近乎O(n^3)的做法使其很容易超时,所以要用二进制优化;
二进制优化,就是将一个物品分解成多个二进制数表示的形式,然后再用01背包求解;
如:32 = 2 + 4 + 8 + 16 + 2;
那这五个物品的价值总和就相当于32,且这五个物品只能选一次;
具体看代码:
#include <iostream>
using namespace std;
int n, m, num;
int w[1000005], c[1000005]; //要开大一点,因为要分解;
int f[1000005];
int main() {
cin >> n >> m; //物品数量和背包容积;
int a, b, num; //每件物品的重量,价值,个数;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a >> b >> num;
for (int j = 1; j <= num; j <<= 1) { // j *= 2;
w[++cnt] = a * j;
c[cnt] = b * j;
num -= j; //这样就可以保证每件物品只能选一次(因为如果选多次就超过了原来的num;
}
if (num) { //如果num不能完全分解,那就把剩下的直接存入;
w[++cnt] = a * num;
c[cnt] = b * num;
}
}
for (int i = 1; i <= cnt; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + c[i]);
}
}
cout << f[m];
return 0;
}
<4> 混合背包;
就是把三种背包混合起来,不同背包用不同方法即可;
但要注意开个结构体存储背包种类;
#include <iostream>
using namespace std;
struct sss {
int w, c, nu; //重量,价值,背包类型;
}e[1000005];
int n, m;
int f[1000005];
int main() {
cin >> m >> n;
int a, b, num; //同上;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a >> b >> num;
if (num == 1) { //只能要一个;
e[++cnt].w = a;
e[cnt].c = b;
e[cnt].nu = 1; //01背包;
} else if (num == 0) { //能要无限个;
e[++cnt].w = a;
e[cnt].c = b;
e[cnt].nu = 2; //完全背包;
} else {
for (int j = 1; j <= num; j <<= 1) { //多重背包的二进制优化;
e[++cnt].w = j * a;
e[cnt].c = j * b;
e[cnt].nu = 1; //01背包;
num -= j;
}
if (num) {
e[++cnt].w = num * a;
e[cnt].c = num * b;
e[cnt].nu = 1;
}
}
}
//预处理后直接按背包种类跑DP就行;
for (int i = 1; i <= cnt; i++) {
if (e[i].nu == 1) {
for (int j = m; j >= e[i].w; j--) {
f[j] = max(f[j], f[j - e[i].w] + e[i].c);
}
} else {
for (int j = e[i].w; j <= m; j++) {
f[j] = max(f[j], f[j - e[i].w] + e[i].c);
}
}
}
cout << f[m];
return 0;
}
<5> 分组背包;
一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn。
这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
其实就是分着跑01背包,用结构体存储,按组号升序排列,然后每组跑倒着的01就行;
模板:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct sss{
int w, c, nu; //nu为组号;
}e[1000005];
int n, m, t;
int f[1000005];
bool cmp(sss x, sss y) {
return x.nu < y.nu; //按组号排序,减小复杂度;
}
int main() {
cin >> m >> n >> t;
memset(f, 0, sizeof(f));
memset(e, 0, sizeof(e));
for (int i = 1; i <= n; i++) {
cin >> e[i].w >> e[i].c >> e[i].nu;
}
sort(e + 1, e + 1 + n, cmp);
for (int i = 1; i <= t; i++) { //枚举组号;
for (int j = m; j >= 0; j--) { //先枚举每一个容积,再枚举数量,因为每组至多选一个,每个容积只能被一个物品更新;这里的j从m到0,每个状态都要更新,为下一组的状态继承做铺垫;
for (int k = 1; k <= n; k++) {
if (j < e[k].w) continue;
if (e[k].nu == i) { //如果在第i组;
f[j] = max(f[j], f[j - e[k].w] + e[k].c);
}
}
}
}
cout << f[m];
return 0;
}
思考:如果是最少选一件呢?
<6> 输出方案;
开一个g数组(维数依据题意而定)记录下标状态转移需要这个数组的值;
一般采用递归输出或者ans数组倒序输出;
具体见线性DP;
<7> 有依赖的DP;
现在还不太理解,感觉想树状DP或树上背包;
3、线性DP;
线性DP可以说是应用最广泛的DP了,在后面写坐标DP时,感觉坐标DP就是线性DP的一类,有的区间DP也可以和线性DP结合着做;
线性DP的状态也是一层层转移而来,每层互不影响,如f[i][sth.]可以由f[i - 1][sth.] + value转移而来;
<1> 求最长上升序列并输出路径;
模板:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int a[100005];
int f[100005];
int g[100005];
int n;
void output(int x) { //递归输出序列;
if (x) {
cout << a[x] << ' '; //倒序输出,所以回溯时再输出;
output(g[x]);
}
}
int main() {
memset(a, 0, sizeof(a));
memset(g, 0, sizeof(g));
n = 1;
while(scanf("%d", &a[n]) != EOF) n++;
n--;
for (int i = 1; i <= n; i++) {
f[i] = 1; //当长度(最后一位下标)为1时,最长上升序列长度为1;
}
int ma = -1;
for (int i = n - 1; i >= 1; i--) { //倒序循环,一步步往前更新;
for (int j = i + 1; j <= n; j++) {
if (a[i] < a[j]) {
if (f[i] < f[j] + 1) {
f[i] = f[j] + 1;
g[i] = j;
}
}
ma = max(ma, f[i]);
}
}
cout << ma << endl; //序列最长长度;
ma = -1;
int o = 0;
for (int i = 1; i <= n; i++) {
if (ma < f[i]) {
ma = f[i];
o = i; //找出最大f的下标;
}
}
output(o); //递归输出;
return 0;
}
Copyright2024 复习与回顾 belong to Peppa_Even_Pig(AGP)
更新于2024/2/5 17:53
法律条款——本劳动成果解释权归 Peppa_Even_Pig(AGP) 所有,并已获得个人级专利保护,任何侵权行为都将予以追究!
%%%