Logo

Menu

十七

Archives

2022 / 02

acwing5. 多重背包问题 II(二进制优化）

2022-02-18

acwing #dp
分析如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。那么根据数据范围，这样的时间复杂度是O(n^3),也就是1e+9，这样是毫无疑问是会TLE的思路一个10进制数字可以由二进制数表示，我们把每一种物品都按二进制分堆，并计算每个堆的体积和价值，这样每个堆就是只能使用一次，就变成了
leetcode48. 旋转图像

2022-02-17

leetcode #图形#中等
思路class Solution {public: void rotate(vector<vector<int>>& matrix) { int n=matrix.size(); for(int i=0;i<n;i++){
leetcode47. 全排列 II

2022-02-17

leetcode #dfs#中等
思路对比46题，这里有重复数字，[1，2，2]中[1，2，2]和[1,2,2]是相同的，可以将数组排序，然后遇到相同数字时，判断上一个数字是否已经用过，如果用过了，那么就跳过这次循环（相当于去重）。class Solution {public: vector<vector<int&
acwing4. 多重背包问题 I

2022-02-17

acwing
acwing3. 完全背包问题

2022-02-17

acwing #dp
leetcode46. 全排列

2022-02-16

leetcode #dfs#中等
class Solution {public: bool flag[10]; vector<vector<int>> ans; vector<int>path; void dfs(vector<int>&nums,int
acwing2.01背包问题

2022-02-16

acwing
朴素版（二维）状态f[i][j]定义：前 ii 个物品，背包容量 jj 下的最优解（最大价值）：当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 NN 件物品，则需要 NN 次决 策，每一次对第 ii 件物品的决策，状态f[i][j]不断由之前的状态更新而来。2.
acwing859. Kruskal算法求最小生成树

2022-02-16

acwing #并查集#图论
#include<iostream>#include<algorithm>using namespace std;const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;int p[N],n,m;struct Edge{ int a,b,w
acwing852. spfa判断负环

2022-02-15

acwing #spfa
#include<iostream>#include<cstring>#include<queue>using namespace std;const int N=1e5+10;int ne[N],e[N],h[N],idx,w[N];int n,m,dist[N
acwing851. spfa求最短路

2022-02-15

acwing #spfa
#include<iostream>#include<cstring>#include<queue>using namespace std;const int N=1e5+10;int ne[N],e[N],h[N],idx,w[N];int n,m,dist[N
Previous 35 / 43 Next