2022115828

分类

学习笔记(4) 题解(9)

/ 注册

全部文章（共3篇）

最大子段和问题

P1115 最大子段和思路：经典线性DP，dp[i]表示前i个元素的最大子段和，最后输出max(ma, dp[i])即可 void solve(){ int n; cin >> n; vector<int> a(n + 1), dp(n + 1); for(int...

C++ 动态规划双指针

2023-11-19

0 300

DP问题之背包问题

1：01背包问题问题：给出n个物品，每个物品只能使用一次，每个物品有相应的体积与价值，你可以选择总体积不超过m的物品放入背包，求能得到的最大价值思路：建立一个二维的DP矩阵，dp[i][j]表示把前i个物品装入体积为j的背包能得到的最大价值，从小问题扩展到大问题朴素版： int n, m; i...

C++ 动态规划

2023-10-20

0 278

多重背包

思路：模板题，利用二进制优化 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=100010; int w[N],v[N],dp[N]; int main(){ ios::sy...

C++ 动态规划

2023-07-14

0 349