zzqwtc

未归档

题解(3)

/ 注册

全部文章 / 未归档（共54篇）

01背包原理

01背包每件物品只有一个朴素算法分为两种情况：①不选第i个物品 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] ②选第i个物品状态方程可以由 f [ i − 1 ] [ j − v ] + w f[i-1][j-v] + w f[i−1][j−v]+w...

2021-01-25

0 411

多重背包原理

多重背包每件物品的个数有限制朴素算法与完全背包的朴素算法类似时间复杂度 O ( N ∗ V ∗ S ) O(N*V*S) O(N∗V∗S) 状态转移方程 f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − k ∗ v [...

2021-01-25

0 448

分组背包原理

分组背包类似多重背包，只是将每件物品选几个变成每组物品选哪一个状态转移方程 f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] ) f[i][j] = Ma...

2021-01-25

0 505

线性dp原理

线性DP 数字三角形给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 4 4 ...

2021-01-25

0 441

区间dp原理

区间DP 石子合并设有N堆石子排成一排，其编号为1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不...

2021-01-25

0 585

计数dp原理

计数DP 整数划分一个正整数 n n n可以表示成若干个正整数之和我们将这样的一种表示称为正整数n的一种划分。现在给定一个正整数n，请你求出n共有多少种不同的划分方法。完全背包写法状态表示类似完全背包 1 ～ i 1～i 1～i分为 i i i个物品每个物品的体积为 i ...

2021-01-25

0 385

数位dp

数位统计DP 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0 ~ 9的出现次数。假设 n = a b c d e f g n = abcdefg n=abcdefg 计算 d d d位上 x x x出现的次数 r e s res res记录答案 1、 ( 001 — — a ...

2021-01-25

0 474

状压dp原理

状压DP 蒙德里安的梦想求把 N ∗ M N*M N∗M的棋盘分割成若干个1*2的的长方形，有多少种方案。先考虑横着放的情况竖着放的自然唯一确定状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示第 i i i列的每一行小方格被占用的情况 j j j为二进制...

2021-01-25

0 308

树形dp原理

树形DP 没有上司的舞会状态表示 f [ u ] [ 0 ] f[u][0] f[u][0] : 所有从以u为根的子树中选择,并且不选择这个点的方案 f [ u ] [ 1 ] f[u][1] f[u][1]: 所有从以u为根的子树中选择,并且选择这个点的方案状态计算 u u ...

2021-01-25

0 734

树状数组原理

功能: ①快速求前缀和 O ( l o g n ) O(logn) O(logn) ②修改某一个数 O ( l o g n ) O(logn) O(logn) 操作： ①：建树 void add(int x, int c) { //树状数组的插入操作 for (int i =...

2021-01-25

1 381