深圳-第三期-XP03A-一班-day3
2026-08-05 08:54:04
发布于：广东
29阅读
0回复
0点赞
day3
T120185.爬楼梯
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 动态规划：
* 实现方式：
* 1. 基于递推 （循环）
* 2. 基于递归 （递归）
*
* 1. 从小规模的数据量开始入手，去挖掘大规模与小规模数据量之间的联系
*
*/
/**
* 假设 dp[i] 用于记录爬到 i 号台阶的方案数
* dp[i] = dp[i-1] + dp[i-2]
* dp[0] = 1, dp[1] = 1, dp[2] = 2
*/
ll n;
ll dp[110];
int main() {
cin >> n;
dp[0] = 1, dp[1] = 1, dp[2] = 2;
for (ll i = 3; i <= n; i ++) dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[n] << '\n';
return 0;
}
T129271.石板问题（中等版）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 假设 dp[n] 可以求出第 n 项的方案数，
* 第n项的结果依赖于：n-1、n-2、n-3 的结果
* dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
*
* 从小样例入手，去挖掘大样例与小样例的联系
* dp[1] = 1
* dp[2] = 1
* dp[3] = 2
* dp[4] = 4
* dp[5] = 7
* ...
* dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
*/
ll n;
ll dp[55];
int main() {
cin >> n;
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
for (ll i = 4; i <= n; i ++) dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
cout << dp[n] << '\n';
return 0;
}
A93768.跳跃假期
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 定义：dp[i][j] 表示第 i 天选择 j 方案的情况下的最大愉悦值（最大收益）
* i 的范围是：[1, n]
* j 的范围是：[0, 1, 2] -> [A, B, C]
*/
const ll N = 1e5 + 10;
ll n;
ll a[N][3];
ll dp[N][3];
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++) cin >> a[i][0] >> a[i][1] >> a[i][2];
for (ll i = 1; i <= n; i ++) {
dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i][0];
dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + a[i][1];
dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + a[i][2];
}
cout << max({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
return 0;
}
T117062.彩灯染色
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll N = 1e6 + 10;
ll n;
ll dp[N][2];
int main() {
cin >> n;
dp[1][0] = 1;
dp[1][1] = 2;
for (ll i = 2; i <= n; i ++) {
dp[i][0] = dp[i - 1][1] % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod * 2 % mod;
}
cout << (dp[n][0] + dp[n][1]) % mod << '\n';
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll N = 1e6 + 10;
ll n;
ll dp[N];
int main() {
cin >> n;
dp[1] = 3;
dp[2] = 8;
for (ll i = 3; i <= n; i ++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % mod * 2 % mod;
}
cout << dp[n] << '\n';
return 0;
}
T117137.合法密码串
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll N = 1e6 + 10;
ll n;
ll dp[N];
// dp[i] = dp[i - 1] * 9;
int main() {
cin >> n;
dp[1] = 10;
for (ll i = 2; i <= n; i ++) dp[i] = dp[i - 1] * 9 % mod;
cout << dp[n];
return 0;
}
A93776.额外经验
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10;
ll n;
ll a[N];
ll dp[N][2];
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++) cin >> a[i];
dp[1][0] = 0;
dp[1][1] = a[1];
for (ll i = 2; i <= n; i ++) {
dp[i][0] = max(dp[i - 1][1] + 2 * a[i], dp[i - 1][0]);
dp[i][1] = max(dp[i - 1][0] + a[i], dp[i - 1][1]);
}
cout << max(dp[n][0], dp[n][1]) << '\n';
return 0;
}
T112050.知识闯关大冒险
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* dp[i][0] 记录的是：第 i 个物品不选的时候前面（1~i）所能够累计的
* 最大知识点数量
*
* dp[i][1] 记录的是：第 i 个物品选的时候前面（1~i）所能够累计的
* 最大知识点数量
*
* 第 i 个物品不选，那么最大值是通过：前i-1个物品选与不选的最大值来确定的
* dp[i][0] = max(dp[i-1][0], dp[i-1][1])
* 第 i 个物品选的话，那么最大值是通过：a[i] + dp[i-1][0] 来确定的
*
* dp[i][0] = max(dp[i-1][0], dp[i-1][1])
* dp[i][1] = a[i] + dp[i-1][0]
*
* 又因为：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
*
* 若：dp_[i] 记录的是当前的最大值的话：
* dp_[i] = max(dp[i][0], dp[i][1])
*
* dp[i][0] = dp_[i - 1]
* dp[i][1] = a[i] + dp_[i - 2]
*
* dp_[i] = max(dp[i][0], dp[i][1]) = max(dp_[i - 1], a[i] + dp_[i - 2])
*/
// 方式一：
// const ll N = 1e5 + 10;
// ll n;
// ll a[N];
// ll dp[N][2];
// int main() {
// cin >> n;
// for (ll i = 1; i <= n; i ++) {
// cin >> a[i];
// }
// for (ll i = 1; i <= n; i ++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
// dp[i][1] = a[i] + dp[i-1][0];
// }
// cout << max(dp[n][0], dp[n][1]) << '\n';
// return 0;
// }
// 方式二：
const ll N = 1e5 + 10;
ll n;
ll a[N];
ll dp_[N];
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++) {
cin >> a[i];
}
dp_[1] = a[1];
dp_[2] = max(a[1], a[2]);
for (ll i = 3; i <= n; i ++) {
dp_[i] = max(dp_[i - 1], a[i] + dp_[i - 2]);
}
cout << dp_[n] << '\n';
return 0;
}
T112027.魔法师の进阶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 求最长上升子序列：
* 时间复杂度是：O(n^2)
*
* dp[i] = 1
* dp[i] = if (a[1...j] < a[i]) max(dp[1...j]) + 1
*
* 还有更优秀的算法：O(nlogn)
*/
const ll N = 1e3 + 10;
ll n;
ll a[N];
ll dp[N];
ll mx;
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++) {
cin >> a[i];
dp[i] = 1;
for (ll j = 1; j < i; j ++) {
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
}
mx = max(mx, dp[i]);
}
cout << mx << '\n';
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 求最长上升子序列：
* 时间复杂度是：O(n^2)
*
* dp[i] = 1
* dp[i] = if (a[1...j] < a[i]) max(dp[1...j]) + 1
*
* 还有更优秀的算法：O(nlogn) 二分+贪心
*
* 底层思想：基于贪心的思想去构造一条“伪”上升子序列
*
* 必须要求数组是升序的（降序的话，建议手写二分）
* lower_bound 找到是第一个大于或等于 x 的数的地址
* upper_bound 找到是第一个大于 x 的数的地址
* binary_search 判断 x 是否有出现
*
* ll a[1 ... n]
* auto it = lower_bound(a + 1, a + n + 1, x);
* 如果不存在，返回值是：a + n + 1
*
* auto it = upper_bound(a + 1, a + n + 1, x);
* 如果不存在，返回值是：a + n + 1
*
* if (binary_search(a + 1, a + n + 1, x)) cout << "存在 x\n";
*
* vector<ll> vt;
* auto it = lower_bound(vt.begin(), vt.end(), x);
* 如果不存在，返回值是：vt.end()
*
* auto it = upper_bound(vt.begin(), vt.end(), x);
* 如果不存在，返回值是：vt.end()
*
* if (binary_search(vt.begin(), vt.end(), x)) cout << "存在 x\n";
*/
const ll N = 1e3 + 10;
ll n;
ll a[N];
vector<ll> vt;
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++) cin >> a[i];
for (ll i = 1; i <= n; i ++) {
if (vt.empty()) vt.push_back(a[i]);
else if (vt.back() < a[i]) vt.push_back(a[i]);
else {
// 二分找到第一个大于或等于 a[i] 的数替换他
auto it = lower_bound(vt.begin(), vt.end(), a[i]);
*it = a[i];
}
}
cout << vt.size() << '\n';
return 0;
}
T112028.魔法师の毕业
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 就是定义两个 dp 数组，
* 一个记录：从左往右看的最大上升子序列
* 一个记录：从右往左看的最大上升子序列
*/
const ll N = 1e3 + 10;
ll n;
ll a[N];
ll L[N], R[N];
int main() {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
// 从左往右看的最大上升子序列
for (ll i = 1; i <= n; i ++) {
L[i] = 1;
for (ll j = 1; j < i; j ++)
if (a[j] < a[i]) L[i] = max(L[i], L[j] + 1);
}
// 从右往左看的最大上升子序列
for (ll i = n; i >= 1; i --) {
R[i] = 1;
for (ll j = n; j > i; j --)
if (a[j] < a[i]) R[i] = max(R[i], R[j] + 1);
}
// 枚举中心点
ll mx = 0;
for (ll i = 1; i <= n; i ++) {
mx = max(mx, L[i] + R[i] - 1);
}
cout << n - mx;
return 0;
}
T112033.哥布林的秘宝密码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* dp[i][j] 指的是：
* a[1...i] 与 b[1...j] 的最长公共子序列的长度
*
* 若：a[i] == b[j]
* 则：dp[i][j] = dp[i-1][j-1] + 1
*
* 若：a[i] != b[j]
* 则：dp[i][j] = max(dp[i][j-1], dp[i-1][j])
*/
ll n, m;
string a, b;
ll dp[1010][1010];
int main() {
cin >> a >> b;
n = a.size();
m = b.size();
a = ' ' + a;
b = ' ' + b;
for (ll i = 1; i <= n; i ++) {
for (ll j = 1; j <= m; j ++) {
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
cout << dp[n][m] << '\n';
return 0;
}
最大子段和
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll N = 1e6 + 10;
ll n;
ll a[N];
ll dp[N];
/**
* 分别是：找数组 a[1 ... n] 的最大值|最小值，返回值是地址。
* max_element(a + 1, a + n + 1)
* min_element(a + 1, a + n + 1)
*
* 分别是：找 vector 数组 vt 的最大值|最小值，返回值是地址。
* max_element(vt.begin(), vt.end())
* min_element(vt.begin(), vt.end())
*/
int main() {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 1; i <= n; i ++) {
// if (dp[i - 1] > 0) dp[i] = dp[i - 1] + a[i];
// else dp[i] = a[i];
dp[i] = max(a[i], dp[i - 1] + a[i]);
}
cout << *max_element(dp + 1, dp + n + 1) << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
/**
* 前缀和数组：
* pre[1] = a[1]
* pre[2] = a[1] + a[2]
* pre[3] = a[1] + a[2] + a[3]
* pre[4] = a[1] + a[2] + a[3] + a[4]
* pre[5] = a[1] + a[2] + a[3] + a[4] + a[5]
* pre[6] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
* pre[7] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]
* pre[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]
* pre[9] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9]
* pre[10] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9] + a[10]
* pre[11] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9] + a[10] + a[11]
* ...
* pre[n] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9] + a[10] + a[11] + ... + a[n]
*
* pre[1] = a[1]
* pre[2] = pre[1] + a[2]
* pre[3] = pre[2] + a[3]
* pre[4] = pre[3] + a[4]
* pre[5] = pre[4] + a[5]
* pre[6] = pre[5] + a[6]
* pre[7] = pre[6] + a[7]
* pre[8] = pre[7] + a[8]
* pre[9] = pre[8] + a[9]
* pre[10] = pre[9] + a[10]
* pre[11] = pre[10]+ a[11]
* ...
* pre[n] = pre[n-1] + a[n]
*
* a[1]
* a[2] += a[1]
* a[3] += a[2]
* a[4] += a[3]
* a[5] += a[4]
* a[6] += a[5]
* a[7] += a[6]
* a[8] += a[7]
* a[9] += a[8]
* a[10] += a[9]
* a[11] += a[10]
* ...
* a[n] += a[n-1]
*
* 如果我想要求出 a[l] + ... + a[r] 的和：
* a[l-1] = a[1] + ... + a[l-1]
* a[r] = a[1] + ... + a[l-1] + a[l] + ... + a[r]
* a[l] + ... + a[r] = a[r] - a[l-1]
*/
const ll N = 1e6 + 10;
ll n;
ll a[N];
ll ans = -1e18;
ll mi; // 记录最小前缀和
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++) {
cin >> a[i];
a[i] += a[i - 1]; // 求前缀和数组
ans = max(ans, a[i] - mi); // 最大子段和 = 当前前缀和 - 最小前缀和
mi = min(mi, a[i]); // 更新最小前缀和
}
cout << ans << endl;
return 0;
}
叠甲吧
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll N = 1e3 + 10;
ll n;
ll a[N];
ll dp[N];
ll mx;
int main() {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 1; i <= n; i++) {
dp[i] = a[i];
for (ll j = 1; j < i; j ++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + a[i]);
}
}
mx = max(mx, dp[i]);
}
cout << mx;
return 0;
}
跳石阶
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll N = 1e6 + 10;
ll n, a[N], dp[N];
int main() {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
dp[1] = 0; dp[2] = abs(a[2] - a[1]);
for (ll i = 3; i <= n; i ++) {
dp[i] = min (
dp[i - 1] + abs(a[i] - a[i - 1]),
dp[i - 2] + abs(a[i] - a[i - 2])
);
}
cout << dp[n];
return 0;
}
背包选礼物
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll N = 110;
ll n, m;
ll w[N], v[N];
/**
* 每一件物品都可以选或不选
* 如果我不选的话，就轮到下一件物品来选，然后容量没有变化；
* 如果我选的话，就轮到一件物品来选，但是容量减少了，价值增加了
*/
// dfs(n, m) 可以从 n 件物品中选取合适的物品来构造出不超过容量为 m 的背包的最大价值
// 用数组记忆化：
ll dp[110][100010];
ll dfs(ll n, ll m) {
if (n == 0) return 0;
if (dp[n][m]) return dp[n][m];
// 当前这个物品可以不选
ll t = dfs(n - 1, m);
if (m >= w[n]) t = max(t, dfs(n - 1, m - w[n]) + v[n]);
return dp[n][m] = t;
}
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i++) cin >> w[i] >> v[i];
cout << dfs(n, m) << endl;
return 0;
}
这里空空如也
有帮助，赞一个