YZBPXX

动态规划&md...

acm入门练习(1) c#(1) c++，c实用小函数，操作(20) hash/bkdr hash字符串(2) 动态规划—树形dp(1) 单调栈(1) 图论—bfs(2) 图论—dfs(6) 图论—最小生成树(1) 图论—最短单源路径(5) 字符串—ac自动机(1) 字符串—扩展KMP/KMP(4) 字符串—马拉车(1) 带权并查集(2) 拓扑排序(2) 数据库学习(6) 数据结构—RMQ(5) 数据结构—字典树(1) 数据结构--红黑二叉树(1) 数论(8) 未归档(2) 矩阵快速幂(1) 算法分析(3) 网络流(1) 集训题(2) 题解(33)

/ 注册

全部文章 / 动态规划—背包九讲（共7篇）

CF 741# div2 D

题目描述：给你n个小姐姐的重量和颜值，而且给你几组关系x,y表示x认识y ，现在要邀请她们吃饭，总共邀请的小姐姐的重量不能大于w （可能怕桌子会跨~~）且互相认识的小姐姐要么最多邀请一个要么全部邀请现在想问你邀请来的小姐姐颜值最高是多少分析：...

分组背包

2019-08-15

0 501

分组背包

对于分组背包问题与01背包不同的是物品被分好组了且一个组最多拿一个（也可能出现其他情况，但大致是这样的）其实也很容易想到多加个for遍历这个组拿哪个合适，这里注意多加的for放在第二个，这样保证每个最多选一个 for(int i=1;i<=n;i++){ ...

模版

2019-08-15

0 593

背包02—完全背包

与01不同的点只有一个，就是允许物品多次放入首先分析这个问题得到状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+v[i]*k); 这是最朴素的方法实现代码： for(i=1;i<=n;i++) { ...

2019-07-31

0 437

背包01

经典问题：有n个物品，分别价值为value，重为volume，放入一个m的背包（保证放满）问如何使得价值最大分析：首先从最后那个状态来看 dp[i][j]=max(dp[i-1],dp[i-1][ j-vo[i] ]+va[i])，起始状态显然是dp[0][j]=0，有了起...

2019-07-30

0 558

dp+离散化

https://ac.nowcoder.com/acm/contest/997/F 题目大意：给定n个数a[0],a[1],,,,a[n-1] 现在你要把它变成一个单调的数列并应此作出修改 value=(a[i]-b[i]),(b[i]是修改后的数)&nb...

离散化

2019-07-25

0 587

oj.1677矩形嵌套，动态规划，贪心

#include<iostream> #include<algorithm> #include<cstring> using namespace std; struct node{ int h,w; }rec[30000]; bool cmp(node a,nod...

2019-05-27

0 598

背包问题（递归的使用）

#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int knap(int W[],int T,int n){ if(T==0) return 1; if(T...

2019-03-16

0 403