https://www.luogu.com.cn/training/211#problems
P1216.数字三角形
思路
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
long long f[N][N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= i; j ++ ) {
scanf("%lld", &f[i][j]);
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= i; j ++ ) {
f[i][j] += max(f[i - 1][j], f[i - 1][j - 1]);
}
}
long long res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
printf("%lld", res);
return 0;
}
P1434.滑雪
Acwing 901.滑雪
time limit per test : 1 second
memory limit per test: 64 megabytes
input:standard input
output:standard output
给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
Input
第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。
Output
输出一个整数，表示可完成的最长滑雪长度。
Range
1≤R,C≤300,
0≤矩阵中整数≤10000
Examples
input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
output
23
思路
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m;
int f[N][N], g[N][N];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int fun(int i, int j) {
int &v = f[i][j];
if (v != -1) return v;
v = 1;
for (int k = 0; k < 4; k ++ ) {
int x = dx[k] + i, y = dy[k] + j;
if (x > 0 && x <= n && y > 0 && y <= m && g[i][j] > g[x][y]) {
v = max(v, fun(x, y) + 1);
}
}
return v;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
scanf("%d", &g[i][j]);
}
}
memset(f, -1, sizeof f);
int res = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
res = max(res, fun(i, j));
}
}
printf("%d", res);
return 0;
}
P2196.挖地雷
Acwing 1011.挖地雷
time limit per test : 1 second
memory limit per test: 64 megabytes
input:standard input
output:standard output
在一个地图上有 n 个地窖（n≤200）,每个地窖中埋有一定数量的地雷。
同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。
某人可以从任意一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。
设计一个挖地雷的方案，使他能挖到最多的地雷。
注意：数据保证挖到最多地雷的路线只有一条。
Input
第一行包含整数n，表示地窖的个数。
第二行包含n个整数，依次为每个地窖地雷的个数。
接下来若干行，每行包含两个整数 xi,yi ，表示从 xi 可到 yi ，xi<yi。
最后一行为0 0表示结束。
Output
Range
n≤200
Examples
input
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
output
3-4-5-6
34
思路
代码
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef pair<int, int> PII;
const int N = 210;
bool g[N][N];
int w[N], f[N], p[N], st[N];
signed main() {
int n, a, b, cnt = 0; PII maxv = {0, 0};
scanf("%lld", &n);
for (int i = 1; i <= n; i ++ ) {
scanf("%lld", &w[i]); f[i] = w[i];
}
while (scanf("%lld%lld", &a, &b), a && b) {
g[a][b] = 1;
}
// for (int i = 1; i <= n; i ++ ) { // 洛谷写法
// for (int j = i + 1; j <= n; j ++ ) {
// scanf("%d", &g[i][j]);
// }
// }
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j < i; j ++ ) {
if (g[j][i] && f[i] < f[j] + w[i]) {
f[i] = f[j] + w[i]; p[i] = j;
}
}
if (maxv.fi < f[i]) {
maxv.fi = f[i], maxv.se = i;
}
}
while (p[maxv.se]) {
st[cnt ++] = maxv.se; maxv.se = p[maxv.se]; // 单链并查集
}
st[cnt ++] = maxv.se;
// st[cnt ++] = maxv.se;
// while (true) { // 回溯写法
// for (int i = 1; i <= n; i ++ ) {
// if (g[i][maxv.se] && f[maxv.se] == f[i] + w[maxv.se]) {
// maxv.se = i; st[cnt] = i;
// }
// }
// if (st[cnt] == 0) break;
// cnt ++;
// }
printf("%lld", st[cnt - 1]);
for (int i = cnt - 2; i >= 0; i -- ) {
printf("-%lld", st[i]);
}
puts("");
printf("%lld", maxv.fi);
return 0;
}
P4017.最大食物链计数
Acwing 2716.食物链
time limit per test : 1 second
memory limit per test: 64 megabytes
input:standard input
output:standard output
如图所示为某生态系统的食物网示意图，据图回答此题。
现在给你 n 个物种和 m 条能量流动关系，求其中的食物链条数。
物种的名称为从 1 到 n 编号。
m 条能量流动关系形如
其中 ai bi 表示能量从物种 ai 流向物种 bi，注意单独的一种孤立生物不算一条食物链。
Input
第一行两个整数 n 和 m。
接下来 m 行每行两个整数 ai,bi 描述 m 条能量流动关系。
数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现。
Output
一个整数，即食物网中的食物链条数。
Range
1≤n≤105,
0≤m≤2×105,
保证答案在 int 范围内。
Examples
input
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9
output
9
思路
记录入度和出度，入度为0最佳生产者，出度为0最佳消费者。
问题转化成: 所有左端点入度为0，右端点出度为0的路径的数量。
如图所示就是所有1 -> 5 的走法的和（5种走法）
==洛谷没有考虑，出度为0 入度为0的情况==
代码
Acwing写法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, idx = 0;
int cnt[N];
int e[M], ne[M], h[M];
int d[N], in[N], out[N]; // 动态规划数组d, 入度in, 出度out
void add(int a, int b) {
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
int main() {
int n, m;
queue<int> q;
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++ ) {
int a, b;
scanf("%d%d", &a, &b);
in[b] ++; out[a] ++; add(a, b); // 单链表
}
// 寻找最佳生产者入队
for (int i = 1; i <= n; i ++ ) {
if (!in[i]) {
d[i] = 1;
q.push(i);
} else if (!out[i]) {
cnt[i] = 1;
}
}
// 以所有的最佳生产者为起点广搜
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (in[j] --) { // 入度存在就减去 1 代表删去节点
d[j] = d[j] + d[t];
}
if (in[j] == 0) q.push(j); // 如果入度为 0 就压入队列
}
}
// 寻找所有的最佳消费者累加
long long ans = 0;
for (int i = 1; i <= n; i ++ ) {
if (cnt[i]) {
ans = ans + (long long)d[i];
}
}
printf("%lld", ans);
return 0;
}
P1048 采药
思路
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
long long f[N];
int main() {
int n, m;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ ) {
long long w, v; scanf("%lld%lld", &v, &w);
for (int j = m; j >= v; j -- ) {
f[j] = max(f[j], f[j - v] + w);
}
}
printf("%lld", f[m]);
return 0;
}
P1616 疯狂的采药
思路
01背包公式 f(i,j)=max(f(i−1,j−v)+w,f(i−1,j))
需要用到本层之前的数据需要倒序==防止覆盖== (比如 f(i−1,j−v) 的位置 比 f(i−1,j) 的位置更靠后)
f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,f(i−1,j−2v)+w......)
f(i,j−v)+w=max( f(i−1,j−v)+w,f(i,j−2v)+w......)
f(i,j)=max(f(i−1,j),f(i,j−v)+w) 需要用到本层的数据 f(i,j−v)+w 所以==正序覆盖==
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
long long f[N];
int main() {
int n, m;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ ) {
long long w, v; scanf("%lld%lld", &v, &w);
for (int j = v; j <= m; j ++ ) {
f[j] = max(f[j], f[j - v] + w);
}
}
printf("%lld", f[m]);
return 0;
}
P1802. 5 倍经验日
洛谷 P1802.5 倍经验日
time limit per test : 1 second
memory limit per test: 125 megabytes
input:standard input
output:standard output
现在 小明 拿出了 x 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。
由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 2 个药去打别人，别人却表明 3 个药才能打过，那么相当于你输了并且这两个属性药浪费了。
现在有 n 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。
要求求出最大经验 s，输出 5s。
Input
第一行两个数，n 和 x。
后面 n 行每行三个数，分别表示失败时获得的经验 losei，胜利时获得的经验 wini 和打过要至少使用的药数量 usei。
Output
一个整数，最多获得的经验的五倍。
Range
对于 100% 的数据，保证 0≤n,x≤103，0<losei≤wini≤106，0≤usei≤103。
Examples
input
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
output
1060
思路
题目中提到如果打不过药就都浪费了，但是从大家的解法来看并不会对后续的行为，没有药了影响，所以我也不知道
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
LL f[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int w1, w2, v;
scanf("%d%d%d", &w1, &w2, &v);
for (int j = m; j >= 0; j -- ) {
if (j >= v) f[j] = max(f[j] + (LL)w1, f[j - v] + (LL)w2);
else f[j] += (LL)w1;
}
}
printf("%lld ", (f[m] << 2) + f[m]);
return 0;
}
P1002.过河卒
思路
（1）多开两个边界防止马跳出界
（2）开 long long 防止爆 int
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
long long f[N][N];
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
int main() {
int n, m, a, b;
scanf("%d%d%d%d", &n, &m, &a, &b);
f[0 + 2][0 + 2] = 1;
f[a + 2][b + 2] = -1;
for (int i = 0; i < 8; i ++ ) {
int x = a + 2 + dx[i], y = b + 2 + dy[i];
f[x][y] = -1;
}
for (int i = 0 + 2; i <= n + 2; i ++ ) {
for (int j = 0 + 2; j <= m + 2; j ++ ) {
if (f[i][j] == 0){
if (f[i - 1][j] != -1) f[i][j] += f[i - 1][j];
if (f[i][j - 1] != -1) f[i][j] += f[i][j - 1];
}
}
}
printf("%lld", f[n + 2][m + 2]);
return 0;
}
