网页设计与网站开发期末,宣传网站建设实践报告,旅游网站开发项目介绍,云网站开发文章目录#x1f4ac;前言#x1f3af;week3#x1f332;day10-1背包完全背包多重背包多重背包 II分组背包#x1f332;day2数字三角形 - 线性DP1015. 摘花生 - 数字三角形#x1f332;day3最长上升子序列 - 线性DP1017. 怪盗基德的滑翔翼 - LIS1014.登山 - LIS最长公共子…
文章目录前言week3day10-1背包完全背包多重背包多重背包 II分组背包day2数字三角形 - 线性DP1015. 摘花生 - 数字三角形day3最长上升子序列 - 线性DP1017. 怪盗基德的滑翔翼 - LIS1014.登山 - LIS最长公共子序列 - 线性DPday4最短编辑距离 - 线性DP编辑距离 - 线性DPday5石子合并 - 区间DP整数划分 - 计数DPday6蒙德里安的梦想 - 状压DP最短Hamilton路径day7没有上司的舞会 - 树形DP前言 本文以经典DP入手带你走进DP的大门感受DP的魅力 DP是 重中之重\blue{重中之重}重中之重 它能决定你的最终名次 在比赛中DP是难点也是重点最重要的是它的分值比重大 DP虽难但也有规律可循有大量的例题模板经典DP考题往往会在基本理论的基础上进行变化 考场上要能准确看出是哪种类型的DP就能快速入手尝试突破。 等你掌握DP时就可以自信的和你的对手说什么档次敢和我写一样的DP题 如果对您有帮助的话还请动动小手 点赞收藏⭐️关注❤️ week3
day1
0-1背包
01背包问题 给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作每次操作可以从任意一堆石子中拿取石子每次拿取的石子数量必须包含于集合 S最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式 第一行包含整数 k表示数字集合 S 中数字的个数。
第二行包含 k 个整数其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数其中第 i 个整数表示第 i 堆石子的数量 hi。
输出格式 如果先手方必胜则输出 Yes。
否则输出 No。
数据范围 1≤n,k≤100, 1≤si,hi≤10000 输入样例 2 2 5 3 2 4 7 输出样例 Yes 背包串联多重背包 拆分为 0-1背包
扩谈钱购买时消耗的体积就是物品的价值:v w (还有其他变式) 2023-DP-先会朴素
#include bits/stdc.husing namespace std;const int N 1010;int f[N][N];
int n,m;
int v,w;int main()
{scanf(%d%d,n,m);for(int i 1; i n; i){scanf(%d%d, v, w);for(int j 0; j m; j)if(j v)f[i][j] max(f[i - 1][j], f[i - 1][j - v] w); //可放 可不放else f[i][j] f[i - 1][j]; //放不下当前物品-只能不放}printf(%d, f[n][m]);return 0;
}(优化原理 - 等式错位相减)
#include iostream
#includecstdio//scanf printf
#includealgorithm//maxusing namespace std;const int N 1010;
int n,m;
int v,w;//可边输入边判断, 也可以存下每种物品的体积v[i]和价值w[i]
int f[N];//f[j] 体积为j时的最大价值
int main()
{scanf(%d%d, n, m);for(int i 0; i n; i){scanf(%d%d,v, w); //边输入边转移for(int j m; j v; j --)f[j] max( f[j] , f[j - v] w);}printf(%d, f[m]);return 0;
}数组版
#include iostream
#include algorithmusing namespace std;const int N 1010;int n, m;
int v[N], w[N]; //存物品体积v[N],价值w[N]
int f[N];int main()
{cin n m;for (int i 1; i n; i ) scanf(%d%d, v[i], w[i]);for (int i 1; i n; i )for (int j m; j v[i]; j -- )f[j] max(f[j], f[j - v[i]] w[i]);printf(%d, f[m]);return 0;
}完全背包
有 N 种物品和一个容量是 V 的背包每种物品都有无限件可用。
第 i 种物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。
输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 种物品的体积和价值。
输出格式 输出一个整数表示最大价值。
数据范围 0N,V≤1000 0vi,wi≤1000 输入样例
4 5
1 2
2 4
3 4
4 5输出样例
10二维朴素
const int N 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{cin n m;for(int i 1;i n;i)scanf(%d%d,v[i],w[i]);for(int i 1;i n;i)for(int j 0;j m;j) //体积为j时选择放入的物品{f[i][j] f[i-1][j]; //不能放时保存上一个值if(j v[i]) f[i][j] max(f[i][j] , f[i][j - v[i]] w[i]); //能放时比较最优解}cout f[n][m] endl;return 0;
}一维优化
#includeiostream
#includealgorithmusing namespace std;const int N 1010;int n, m;
int f[N];int main()
{scanf(%d%d, n, m);for(int i 1; i n; i) {int v, w;scanf(%d%d, v, w);for(int j v; j m; j)f[j] max(f[j], f[j - v] w);}printf(%d, f[m]);return 0;
}开数组先读入再枚举计算
#includeisotreamusing namespace std;const int N 1010;
int n,m;
int v[N],w[N],f[N];int main()
{cin n m; //n种物品容量m的背包for(int i 1; i n; i)scanf(%d%d, v[i], w[i]);for(int i 1; i n; i)for(int j v[i]; j m; j) //体积为j时选择放入的物品f[j] max(f[j] , f[j - v[i]] w[i]); //【好记与01背包不同按从小到大枚举体积得max_w】cout f[m] endl;return 0;
}多重背包
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式 输出一个整数表示最大价值。
数据范围 0N,V≤100 0vi,wi,si≤100 输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例 10
一、状态表示f[i][j]
1. 集合从前i个物品中选,且总体积不超过j的所有方案的集合.
2. 属性最大值二、状态计算
1. 思想-----集合的划分
2. 集合划分依据根据第i个物品有多少个来划分.含0个、含1个···含k个.
状态表示与完全背包朴素代码一样均为
f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);时间复杂度O(n∗v∗s)最精简版-边读入边计算【思想拆成0-1背包判断】
#include iostreamusing namespace std;const int N 1010;int f[N];
int n, m;
int v, w, s;int main()
{scanf(%d%d, n, m);while(n--)//n之后没用,可以n-- , 也可for(int i 1; i n; i){scanf(%d%d%d, v, w, s);for(int i 1;i s; i)//拆成s件相同价值的物品 -- s次0-1背包计算for(int j m; j v ; j--)f[j] max(f[j], f[j - v] w);}printf(%d, f[m]);
}朴素版
#include iostream
#include algorithmusing namespace std;
const int N 110;int v[N], w[N], s[N];
int f[N][N];
int n, m;int main(){cin n m;for(int i 1; i n; i ) cin v[i] w[i] s[i];for(int i 1; i n; i ){//枚举种类for(int j 1; j m; j ){//枚举体积for(int k 0; k s[i]; k ){//枚举件数if(j k * v[i]){//转移限制条件f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);//取k件物品减对应k件物品价值}}}}cout f[n][m] endl;return 0;
}多重背包 II
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式 输出一个整数表示最大价值。
数据范围 0N≤1000 0V≤2000 0vi,wi,si≤2000 提示 本题考查多重背包的二进制优化方法。
输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例 10 二进制优化 0-1背包模板 思想举例 7 的二进制111 3位选不选0/1 1 2 4可组合成 0-7
但取 s 10 非2^n - 1
就用 s - 1 - 2 - 4 3 8 ,已拆分的1 2 4对应二进制1 10 100 【剩下的3单独加入集合】1 2 4 3 -- 枚举 (全不选) 0 - 10 (全选) 优化完能解决: 枚举v[i]物品体积 * s[i]每种物品个数 * m体积限制 4e10 不开数组版-边读入边计算[模板] a, b, s : 每种物品: 体积v 价值w 数量s #includeiostream
#includecstdiousing namespace std;const int N 12010, M 2010;//N:拆分后物品件数最多12000 , M : 背包体积int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 背包体积 M , f[j]: 体积为j时的最大价值int main()
{scanf(%d%d, n, m); //n件种类组合m总体积int cnt 0; //记录拆分后种类 ,最后 n cntfor(int i 1; i n; i){int a, b, s;//【开局部变量的好处就是可以在不同作用域内有多个重名但不冲突】 scanf(%d%d%d, a, b, s); //不能用v,w和数组重名 int k 1; //(乘积用1)拆分初始项1 k * 2 1 2 4 1 10 100...while(k s){cnt ;v[cnt] a * k; // 原来共 a * s 拆成 a * 1 a * 2 a * 4 .... w[cnt] b * k;s - k;k * 2; //也可以 k 1}if(s 0)// 最后若非 2^n-1 , 取 s 与 (2^n-1) 的余数 如 10 1 2 4 ... 3 ,则最后一项取 3v,3w{cnt ;v[cnt] a * s; w[cnt] b * s;}}n cnt; //*每个拆分的背包占体积不同 -- 种类不同变多 //拆项后转化成01背包一维优化for(int i 1; i n ; i )for(int j m ; j v[i]; j --)f[j] max(f[j], f[j - v[i]] w[i]);printf(%d, f[m]);return 0;
}开数组版-存每种物品属性 a[N], b[N], s[N];每种物品: 体积v 价值w 数量s #includeiostreamusing namespace std;const int N 12010, M 2010;//N:拆分后物品件数最多12000 , M : 背包体积int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 背包体积 M , f[j]: 体积为j时的最大价值
int a[N], b[N], s[N];//每种物品: 体积v 价值w 数量sint main()
{scanf(%d%d, n, m); //n件种类组合m总体积int cnt 0; //记录拆分后种类 ,最后 n cntfor(int i 1;i n;i) scanf(%d%d%d, a[i], b[i], s[i]); //不能用v,w和数组重名for(int i 1;i n;i){int k 1; //(乘积用1)拆分初始项1 k * 2 1 2 4 1 10 100...while(k s[i]){cnt ;v[cnt] a[i] * k; // 原来共 a * s 拆成 a * 1 a * 2 a * 4 .... w[cnt] b[i] * k;s[i] - k;k * 2; //也可以 k 1}if(s[i] 0)// 最后若非 2^n-1 , 取 s 与 (2^n-1) 的余数 如 10 1 2 4 ... 3 ,则最后一项取 3v,3w{cnt ;v[cnt] a[i] * s[i]; w[cnt] b[i] * s[i];}}n cnt; //*每个拆分的背包占体积不同 -- 种类不同变多 //拆项后转化成01背包一维优化for(int i 1;i n ;i )for(int j m ;j v[i];j --)f[j] max(f[j],f[j-v[i]] w[i]);printf(%d, f[m]);return 0;
}分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个同一组内的物品最多只能选一个。 每件物品的体积是 vij价值是 wij其中 i 是组号j 是组内编号。
求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。
输出最大价值。
输入格式 第一行有两个整数 NV用空格隔开分别表示物品组数和背包容量。
接下来有 N 组数据
每组数据第一行有一个整数 Si表示第 i 个物品组的物品数量 每组数据接下来有 Si 行每行有两个整数 vij,wij用空格隔开分别表示第 i 个物品组的第 j 个物品的体积和价值 输出格式 输出一个整数表示最大价值。
数据范围 0N,V≤100 0Si≤100 0vij,wij≤100 输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5输出样例
8f[j]:只从前i组物品中选, 且总体积不超过j的选法 不选:f[j] , 选f[j - v[i][k]] w[i][k] 比较取max继续转移下一个状态 #include iostream
#include algorithmusing namespace std;const int N 110;int n, m;
int v[N][N], w[N][N], s[N]; //二维存入物品体积、价值 v[i][k] (第i组第k件物品体积)
int f[N]; //f[j] : 只从前i组物品中选, 且总体积不超过j的选法int main()
{scanf(%d%d, n, m);//依题读入for (int i 0; i n; i ){scanf(%d, s[i]);//存每组物品数量for (int j 0; j s[i]; j )//读入每组物品下标从0开始scanf(%d%d, v[i][j], w[i][j]);}for (int i 0; i n; i )for (int j m; j 0; j -- ) //0-1背包模板 【注意写法k在下面枚举,此时下标还无法表示:只能写j 0(且j与k枚举顺序不能变)】for (int k 0; k s[i]; k ) //每组物品下标从0开始if (v[i][k] j) //条件限制能放的下此物品 v[i][k] : 第i组的第k件物品f[j] max(f[j], f[j - v[i][k]] w[i][k]); //选或不选printf(%d, f[m]);return 0;
}day2
数字三角形 - 线性DP
给定一个如下图所示的数字三角形从顶部出发在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点一直走到底层要求找出一条路径使路径上的数字的和最大。 73 88 1 02 7 4 44 5 2 6 5输入格式 第一行包含整数 n表示数字三角形的层数。
接下来 n 行每行包含若干整数其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式 输出一个整数表示最大的路径数字和。
数据范围 1≤n≤500, −10000≤三角形中的整数≤10000 输入样例
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5输出样例
30思路 路径从起点走到终点的距离 终点走回起点的距离 逆序从最后一行开始走a[n][i] --a[1][1] ,只需要一维最终max都转移到f[1] : 以第n行第i列走到[1,1]的最大值max 往上转移转移到上层[i][j] , 则下层相对于上层的下标为[i 1][j], [i 1][j 1] i用循环等效对应, f[j]一维枚举计算[j]与[j1]最后一轮i 1,最终 f[1] 存转移到 a[1][1] 的max 朴素版
#include iostream
#include algorithmusing namespace std;const int N 510, INF 1e9;int n;
int a[N][N];//存三角形
int f[N][N];//f[n][i] : 到第n个点的路径之和maxint main()
{scanf(%d, n);for (int i 1; i n; i ) //dp用到下标i - 1 从1开始for (int j 1; j i; j )scanf(%d, a[i][j]);//i 1更准确, 0当然也可以初始-INF需包括三角形及其边界for (int i 1; i n; i )//下三角形 //【 因为题目n∈[-1e4,1e4], 存在负数 】, 所以应该将两边也设为-INFfor (int j 0; j i 1; j )f[i][j] -INF;//求最大边界不影响 取负无穷-INFf[1][1] a[1][1];//下标不越界初始起点需赋值for (int i 2; i n; i )//2开始for (int j 1; j i; j )f[i][j] max(f[i - 1][j - 1], f[i - 1][j]) a[i][j];//选取上一个状态大的 此状态值//等效f[i][j] max(f[i - 1][j - 1] a[i][j], f[i - 1][j] a[i][j]);int res -INF;//求最大, 初始负无穷-INFfor (int i 1; i n; i ) res max(res, f[n][i]); //最后一行都是最终状态选取maxprintf(%d\n, res);return 0;
}从下往上优化
#includeiostream
#includecstdio
#includealgorithmusing namespace std;const int N 1010;int f[N];
int a[N][N];int main()
{int n;scanf(%d, n);for(int i 1; i n; i)//读入三角形, 为了不判断边界:从1开始for(int j 1; j i; j)scanf(%d, a[i][j]);for(int i n; i 1; i--) //推导后的一维优化in 逆序从最后一行开始, j正序 从最后一行走到顶【顶只有1个】for(int j 1; j i; j)f[j] max(f[j], f[j 1]) a[i][j];//往上走转移下标为j和j 1printf(%d, f[1]);return 0;
}1015. 摘花生 - 数字三角形
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)从西北角进去东南角出来。
地里每个道路的交叉点上都有种着一株花生苗上面有若干颗花生经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式 第一行是一个整数T代表一共有多少组数据。 接下来是T组数据。 每组数据的第一行是两个整数分别代表花生苗的行数R和列数 C。 每组数据的接下来R行数据从北向南依次描述每行花生苗的情况。每行数据有C个整数按从西向东的顺序描述了该行每株花生苗上的花生数目M。 输出格式 对每组输入数据输出一行内容为Hello Kitty能摘到得最多的花生颗数。 数据范围
1≤T≤100 1≤R,C≤100, 0≤M≤1000
输入样例
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5输出样例
8
16#include iostream
#include algorithm //需记库
using namespace std;const int N 105;int n,m;
int w[N][N],f[N][N];int main(){int T;scanf(%d,T);while(T--){scanf(%d%d,n,m);for(int i 1;i n;i)for(int j 1;j m;j)scanf(%d,w[i][j]);for(int i 1;i n;i)for(int j 1;j m;j)f[i][j] max(f[i-1][j],f[i][j-1])w[i][j];printf(%d\n,f[n][m]);}return 0;
} day3
最长上升子序列 - 线性DP
给定一个长度为 N 的数列求数值严格单调递增的子序列的长度最长是多少。
输入格式 第一行包含整数 N。
第二行包含 N 个整数表示完整序列。
输出格式 输出一个整数表示最大长度。
数据范围 1≤N≤1000 −10910^9109≤数列中的数≤10910^9109 输入样例
7
3 1 2 1 8 5 6输出样例
4集合划分f[i]为以a[i]结尾的最长上升子序列 #include iostream
#include algorithmusing namespace std;const int N 1010;int n;
int a[N];
int f[N];int main()
{scanf(%d, n);for (int i 1; i n; i ) scanf(%d, a[i]);int res 0;for (int i 1; i n; i ){f[i] 1;//以i结尾的子序列初始长度为本身 1for (int j 1; j i; j )if (a[i] a[j])//以i结尾子序列 以j结尾的子序列 1f[i] max(f[i], f[j] 1);res max(res, f[i]);}printf(%d, res);return 0;
}1017. 怪盗基德的滑翔翼 - LIS
怪盗基德是一个充满传奇色彩的怪盗专门以珠宝为目标的超级盗窃犯。
而他最为突出的地方就是他每次都能逃脱中村警部的重重围堵而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天怪盗基德像往常一样偷走了一颗珍贵的钻石不料却被柯南小朋友识破了伪装而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。
不得已怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线每幢建筑的高度各不相同。
初始时怪盗基德可以在任何一幢建筑的顶端。
他可以选择一个方向逃跑但是不能中途改变方向因为中森警部会在后面追击。
因为滑翔翼动力装置受损他只能往下滑行即只能从较高的建筑滑翔到较低的建筑。
他希望尽可能多地经过不同建筑的顶部这样可以减缓下降时的冲击力减少受伤的可能性。
请问他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)
输入格式 输入数据第一行是一个整数K代表有K组测试数据。
每组测试数据包含两行第一行是一个整数N代表有N幢建筑。第二行包含N个不同的整数每一个对应一幢建筑的高度h按照建筑的排列顺序给出。
输出格式 对于每一组测试数据输出一行包含一个整数代表怪盗基德最多可以经过的建筑数量。
数据范围 1≤K≤100, 1≤N≤100, 0h10000 输入样例
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10输出样例
6
6
9方向确定就只能往一个方向跳左/右 如图起点a[i] ,最长距离就是以a[i] 结尾的最长上升子序列 【图形先上升再下降则右边往左看为逆LIS 左—右 ,逆序LIS 起点n i- -,j- -
简记正向反向求解LIS 比较得max逆序 起点n i--,j-- i,j意义与正向一样不变//不用res0 正反方向取max for(int i n; i ;i--) //i 0{f[i] 1;for(int j n;j i;j --)if(a[i] a[j])f[i] max(f[i] , f[j] 1); res max(res,f[i]); //算出一个f[i]就比较一次 }#includebits/stdc.h#includealgorithm
using namespace std;const int N 1010;int n,T;
int a[N],f[N];
int main()
{int T;scanf(%d,T);while(T--){scanf(%d,n);for(int i 1;i n;i) scanf(%d,a[i]); //正向求解LISint res 0;for(int i 1;i n;i){f[i] 1;for(int j 1;j i;j )if(a[j] a[i])f[i] max(f[i] , f[j] 1); res max(res,f[i]); //算出一个f[i]就比较一次 }//不用res0 正反方向取max for(int i n; i ;i--) //i 0{f[i] 1;for(int j n;j i;j --)if(a[i] a[j])f[i] max(f[i] , f[j] 1); res max(res,f[i]); //算出一个f[i]就比较一次 }printf(%d\n,res); }return 0;
}
1014.登山 - LIS
题目描述
五一到了ACM队组织大家去登山观光队员们发现山上一个有N个景点并且决定按照顺序来浏览这些景点即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯就是不连续浏览海拔相同的两个景点并且一旦开始下山就不再向上走了。
队员们希望在满足上面条件的同时尽可能多的浏览景点你能帮他们找出最多可能浏览的景点数么
输入格式
第一行包含整数N表示景点数量。
第二行包含N个整数表示每个景点的海拔。
输出格式
输出一个整数表示最多能浏览的景点数。
数据范围
2≤N≤1000
输入样例
8
186 186 150 200 160 130 197 220输出样例
4按编号递增顺序浏览 -- 必须是子序列 先严格上升再严格下降 一旦开始下降就不能上升了 分类以a[k]为极值点转折的子序列的max正反-1有一个共同重叠点 简记 a[k]的max上升存f[i],下降存g[i] res max(res , f[i] g[i] - 1)#includebits/stdc.h#includealgorithm
using namespace std;const int N 110;int n,T;
int a[N];
int g[N],f[N];
int main()
{scanf(%d,n);for(int i 1;i n;i) scanf(%d,a[i]); //正向求解LIS存到f[i] for(int i 1;i n;i){f[i] 1;for(int j 1;j i;j )if(a[j] a[i])f[i] max(f[i] , f[j] 1); }//反向求解LIS 存到g[i] for(int i n;i;i--){g[i] 1;for(int j n;j i;j--)if(a[i] a[j])g[i] max(g[i], g[j] 1);} int res 0;for(int i 1;i n;i) res max(res , f[i] g[i] - 1);printf(%d\n,res); return 0;
}
最长公共子序列 - 线性DP
给定两个长度分别为 N 和 M 的字符串 A 和 B求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式 第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串表示字符串 A。
第三行包含一个长度为 M 的字符串表示字符串 B。
字符串均由小写字母构成。
输出格式 输出一个整数表示最大长度。
数据范围 1≤N,M≤1000 输入样例
4 5
acbd
abedc输出样例
3#include iostream
#include algorithmusing namespace std;const int N 1010;int n, m;
char a[N], b[N];
int f[N][N];int main()
{scanf(%d%d, n, m);scanf(%s%s, a 1, b 1);//转移方程用到下标1,从1开始for (int i 1; i n; i )for (int j 1; j m; j ){f[i][j] max(f[i - 1][j], f[i][j - 1]);//不相等有一个指针向前移动,i或j, 选取转移后的maxif (a[i] b[j]) f[i][j] max(f[i][j], f[i - 1][j - 1] 1);//两个字符相等,双指针继续判断下一位//else f[i][j] max(f[i - 1][j] , f[i][j - 1]); //按逻辑写这里 }printf(%d\n, f[n][m]);return 0;
}day4
最短编辑距离 - 线性DP
给定两个字符串 A 和 B现在要将 A 经过若干操作变为 B可进行的操作有
删除–将字符串 A 中的某个字符删除。 插入–在字符串 A 的某个位置插入某个字符。 替换–将字符串 A 中的某个字符替换为另一个字符。 现在请你求出将 A 变为 B 至少需要进行多少次操作。
输入格式 第一行包含整数 n表示字符串 A 的长度。
第二行包含一个长度为 n 的字符串 A。
第三行包含整数 m表示字符串 B 的长度。
第四行包含一个长度为 m 的字符串 B。
字符串中均只包含大小写字母。
输出格式 输出一个整数表示最少操作次数。
数据范围 1≤n,m≤1000 输入样例
10
AGTCTGACGC
11
AGTAAGTAGGC输出样例
4题意: 每次操作可改变一个元素[增 删 改], 求使得a[]与b[]相等的最少操作次数 集合表示 f[i][j] : a1......ai与b1......bj相等匹配a_1 ...... a_i 与 b_1 ...... b_j 相等匹配a1......ai与b1......bj相等匹配 状态划分 增 删 改 增a[i]与b[j]中,a的前i个与b的前j−1个匹配a需增添一个与b[j]相等的元素,对应f[i−1][j]1a[i]与b[j]中, a的前i个与b的前j-1个匹配a需增添一个与b[j]相等的元素, 对应f[i - 1][j] 1a[i]与b[j]中,a的前i个与b的前j−1个匹配a需增添一个与b[j]相等的元素,对应f[i−1][j]1 删$a[i]与b[j]中,a的前i-1个与b的前j个匹配需删除a[i], 对应f[i][j - 1] 1 $ 改:【分两种情况 加0 或 加1】 ~ ① a[i]与b[j]中,a的前i−1个与b的前j−1个匹配需修改a[i],使得a[i]b[j],对应f[i−1][j−1]1~a[i]与b[j]中,a的前i-1个与b的前j-1个匹配需修改a[i],使得a[i] b[j], 对应f[i-1][j-1] 1 a[i]与b[j]中,a的前i−1个与b的前j−1个匹配需修改a[i],使得a[i]b[j],对应f[i−1][j−1]1 ~ ② a[i]与b[j]中,a的前i−1个与b的前j−1个匹配且a[i]b[j]则无需操作,对应f[i−1][j−1]0~a[i]与b[j]中,a的前i-1个与b的前j-1个匹配且a[i] b[j] 则无需操作, 对应f[i-1][j-1] 0 a[i]与b[j]中,a的前i−1个与b的前j−1个匹配且a[i]b[j]则无需操作,对应f[i−1][j−1]0 边界:f[0][i]a增加i次变成b,f[i][0]a删除i次变成b~f[0][i]a增加i次变成b, f[i][0]a删除i次变成b f[0][i]a增加i次变成b,f[i][0]a删除i次变成b #include iostream
#include algorithmusing namespace std;const int N 1010;int n, m; //strlen(a), strlen(b)
char a[N], b[N];
int f[N][N];int main()
{scanf(%d%s, n, a 1); //【转移方程涉及 i - 1为了省去边界判断, 最好初始化从1开始】scanf(%d%s, m, b 1); //[否则影响如求min碰到边界0则被边界更新为0,出错]//边界for (int i 0; i m; i ) f[0][i] i; //a前0个字符与b的前i个字符匹配需要添加i次for (int i 0; i n; i ) f[i][0] i; //a前i个字符与b的前0个字符匹配需要删除i次for (int i 1; i n; i )for (int j 1; j m; j ){f[i][j] min(f[i - 1][j] 1, f[i][j - 1] 1); //增, 删//if (a[i] b[j]) f[i][j] min(f[i][j], f[i - 1][j - 1]); //else f[i][j] min(f[i][j], f[i - 1][j - 1] 1); f[i][j] min(f[i][j], f[i - 1][j - 1] (a[i] ! b[j]) ); //改的两种情况简写(表达式返回值)}printf(%d\n, f[n][m]); //把a的前n个字母变成b的前m个字母return 0;
}编辑距离 - 线性DP
给定 n 个长度不超过 10 的字符串以及 m 次询问每次询问给出一个字符串和一个操作次数上限。
对于每次询问请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式 第一行包含两个整数 n 和 m。
接下来 n 行每行包含一个字符串表示给定的字符串。
再接下来 m 行每行包含一个字符串和一个整数表示一次询问。
字符串中只包含小写字母且长度均不超过 10。
输出格式 输出共 m 行每行输出一个整数作为结果表示一次询问中满足条件的字符串个数。
数据范围 1≤n,m≤1000,
输入样例
3 2
abc
acd
bcd
ab 1
acbd 2输出样例
1
3多次求最短编辑距离【封装】 思路 求出最短编辑距离 判断 是否不超过上限limit : if(编辑距离limit)res;~if(编辑距离 limit) res ; if(编辑距离limit)res;
#include iostream
#include algorithm
#include string.husing namespace std;const int N 15, M 1010;int n, m;
int f[N][N];
char str[M][N];int edit_distance(char a[], char b[]) //求a[] 变成 b[] 的最少操作次数
{int la strlen(a 1), lb strlen(b 1); //注意首地址从1开始for (int i 0; i lb; i ) f[0][i] i;for (int i 0; i la; i ) f[i][0] i;for (int i 1; i la; i )for (int j 1; j lb; j ){f[i][j] min(f[i - 1][j] 1, f[i][j - 1] 1); //增, 删f[i][j] min(f[i][j], f[i - 1][j - 1] (a[i] ! b[j])); //改的两种情况-精妙简写}return f[la][lb];
}int main()
{scanf(%d%d, n, m);for (int i 0; i n; i ) scanf(%s, str[i] 1); //每行从1开始 存入awhile (m -- ) //每轮询问【str[][]中有多少个a满足操作次数 limit变成b】{char s[N];int limit;scanf(%s%d, s 1, limit); //读入b 和 操作次数限制limit int res 0; for (int i 0; i n; i )if (edit_distance(str[i], s) limit) //【注意传入从0开始对应函数内部才为从1开始取长度】res ;printf(%d\n, res);}return 0;
}day5
石子合并 - 区间DP
设有 N 堆石子排成一排其编号为 123…N。
每堆石子有一定的质量可以用一个整数来描述现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2 我们可以先合并 1、2 堆代价为 4得到 4 5 2 又合并 12 堆代价为 9得到 9 2 再合并得到 11总代价为 491124
如果第二步是先合并 23 堆则代价为 7得到 4 7最后一次合并代价为 11总代价为 471122。
问题是找出一种合理的方法使总的代价最小输出最小代价。
输入格式 第一行一个数 N 表示石子的堆数 N。
第二行 N 个数表示每堆石子的质量(均不超过 1000)。
输出格式 输出一个整数表示最小代价。
数据范围 1≤N≤300 输入样例
4
1 3 5 2输出样例
22限制每次只能合并相邻的两堆 根据限制划分 第k堆为最后一次合并: f[l][k]f[k1][r]s[r]−s[l−1];f[l][k] f[k 1][r] s[r] - s[l - 1];f[l][k]f[k1][r]s[r]−s[l−1];(区间和代价用前缀和计算) #include iostream
#include algorithmusing namespace std;const int N 310;int n;
int s[N];
int f[N][N];int main()
{scanf(%d, n);for (int i 1; i n; i )//读入 , 初始化前缀和{scanf(%d, s[i]);s[i] s[i - 1];}//【区间枚举】for (int len 2; len n; len )//枚举合并的区间长度 【区间长度是1则不需要代价, 直接从2开始枚举】for (int i 1; i len - 1 n; i )//枚举起点, 最后一个位置 n()不越界{int l i, r i len - 1;f[l][r] 1e8;//求最小, 初始需超过max边界值 (未初始化则全局为0,算出全为0...)for (int k l; k r; k )f[l][r] min(f[l][r], f[l][k] f[k 1][r] s[r] - s[l - 1]);}//先不管最后一次合并的代价, 则代价转移为k点printf(%d\n, f[1][n]);return 0;
}整数划分 - 计数DP
一个正整数 n 可以表示成若干个正整数之和形如nn1n2…nknn_1n_2…n_knn1n2…nk其中 n1≥n2≥…≥nk,k≥1n_1≥n_2≥…≥n_k,~k≥1n1≥n2≥…≥nk, k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n请你求出 n 共有多少种不同的划分方法。
输入格式 共一行包含一个整数 n。
输出格式 共一行包含一个整数表示总划分数量。
由于答案可能很大输出结果请对 109710^971097 取模。
数据范围 1≤n≤1000 输入样例:
5输出样例
7y总 佬の思路 把1,2,3, … n分别看做n个物体的体积,问恰好能装满总体积为n的背包的总方案数 (枚举这n个物体均无数量限制,用完全背包模板)
①完全背包解法 状态表示 f[i][j]表示只从1~i中选且总和等于j的方案数
状态转移方程: f[i][j] f[i - 1][j] f[i][j - i]; 同完全背包可以一维优化去掉i f[j] f[j] f[j - i]
#include iostream
#include algorithmusing namespace std;const int N 1010, mod 1e9 7;int n;
int f[N];int main()
{cin n;f[0] 1;for (int i 1; i n; i )for (int j i; j n; j )//从i开始正序f[j] (f[j] f[j - i]) % mod; //【不懂推就记住】可以由上一个状态等价转移cout f[n] endl;return 0;
}②其他算法 状态表示 f[i][j]表示总和为i总个数为j的方案数
状态转移方程 f[i][j] f[i - 1][j - 1] f[i - j][j];
#include iostream
#include algorithmusing namespace std;const int N 1010, mod 1e9 7;int n;
int f[N][N];int main()
{cin n;f[1][1] 1;for (int i 2; i n; i )for (int j 1; j i; j )f[i][j] (f[i - 1][j - 1] f[i - j][j]) % mod;int res 0;for (int i 1; i n; i ) res (res f[n][i]) % mod;cout res endl;return 0;
}day6
蒙德里安的梦想 - 状压DP
求把 N×M 的棋盘分割成若干个 1×2 的长方形有多少种方案。
例如当 N2M4 时共有 5 种方案。当 N2M3 时共有 3 种方案。
如下图所示 输入格式 输入包含多组测试用例。
每组测试用例占一行包含两个整数 N 和 M。
当输入用例 N0M0 时表示输入终止且该用例无需处理。
输出格式 每个测试用例输出一个结果每个结果占一行。
数据范围 1≤N,M≤11 输入样例
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0输出样例
1
0
1
2
3
5
144
51205能从k转移到j即能从前一个状态转移过来需满足 ① (j k) 0 没有冲突横着放占两格相邻状态转移不能为同一行 ② j | k 不存在连续奇数个0, 剩下的0能够放下竖着的两格才能填满 朴素写法1000ms
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 12, M 1 N;int n, m;
long long f[N][M]; //注意枚举种类很多开LL
bool st[M]; //当前这一列所有的空着的【连续的0是否都为偶数是否合法】int main() //核心枚举横着放, 再空位都放竖的(代码枚举横放)
{while (cin n m, n || m) //n, m都为0停止{for (int i 0; i 1 n; i ) // i 2^n 枚举所有方案每行格子选或不选 0或1{int cnt 0;//统计当前这一段连续0的个数【0为空着的位置】st[i] true;//假设此方案可行truefor (int j 0; j n; j ) //每轮i共选n位(二进制数), 取i的二进制每位判断选或不选 if (i j 1) //i的此位选择1选择放横的判断i的二进制的j - 1位是否为1{if (cnt 1) st[i] false; //前面有连续的奇数个0, 不能成功转移, 此状态falsecnt 0; //重新计数}else cnt ; //不选为0 if (cnt 1) st[i] false; //最后一段连续个0,若是奇数个0,状态转移失败【剩下的位置放竖的必须剩余偶数个0】 }memset(f, 0, sizeof f); //f每轮需要重新置0【多轮输入】f[0][0] 1; //不可能f[-1][0]转移过来, 空集也代表一种方案【不用填变相填满】for (int i 1; i m; i ) //枚举所有列for (int j 0; j 1 n; j ) //枚举此列所有选或不选状态for (int k 0; k 1 n; k ) //枚举前一列的所有二进制排列状态if ((j k) 0 st[j | k]) //j为转移后的状态, k为转移前的状态f[i][j] f[i - 1][k]; //加上之前能转移的方案数cout f[m][0] endl; //能转移到m列,且f[m][0]不会捅出来, 才是一个合法方案}return 0;
}去除无效状态的优化写法230ms
#include cstring
#include iostream
#include algorithm
#include vectorusing namespace std;typedef long long LL;const int N 12, M 1 N; //枚举所有状态2^n 【二进制位选或不选】int n, m;
LL f[N][M]; //种类很多 LL
vectorint state[M]; //存能转移到state[]的状态(存前一个状态)
bool st[M]; //st预处理无效状态 所有二进制选择方案的状态是否合法int main()
{while (cin n m, n || m) //n, m都为0停止{for (int i 0; i 1 n; i ){int cnt 0; //统计当前方案每一段连续0的个数【0为空着的位置】bool is_valid true; //此方案是否有效for (int j 0; j n; j ) //每轮i共选n位(二进制数), 取i的二进制每位判断选或不选 if (i j 1) //i的二进制的第j - 1位是否为1 i 1 个位{if (cnt 1) //连续的0为奇数个{is_valid false; //方案无效break; }// cnt 0; y总写了, 但是my发现这肯定不会执行}else cnt ;if (cnt 1) is_valid false;st[i] is_valid; //st默认初始化为false 只有is_valid 为true才会标记为合法转移方案}for (int i 0; i 1 n; i ) //减少时间复杂度【预处理所有二进制方案的state状态】{state[i].clear(); //【多轮输入注意清空】for (int j 0; j 1 n; j )if ((i j) 0 st[i | j]) //符合转移规则state[i].push_back(j); // j为前一个状态能转移到i }memset(f, 0, sizeof f);f[0][0] 1;//空集也代表一种方案【不用填变相填满】for (int i 1; i m; i ) //枚举for (int j 0; j 1 n; j ) //枚举此列所有选与不选状态for (auto k : state[j]) //枚举前一列的二进制排列所有状态【已经预处理状态,累加计算合法状态就行】f[i][j] f[i - 1][k]; //加上前一个状态i-1的方案数 k state[j] :表示k转移到jcout f[m][0] endl; //能转移到m列,且f[m][0]不会捅出来, 才是一个合法方案}return 0;
}最短Hamilton路径
给定一张 n 个点的带权无向图点从 0∼n−1 标号求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式 第一行输入整数 n。
接下来 n 行每行 n 个整数其中第 i 行第 j 个整数表示点 i 到 j 的距离记为 a[i,j]。
对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x] 并且 a[x,y]a[y,z]≥a[x,z]。
输出格式 输出一个整数表示最短 Hamilton 路径的长度。
数据范围 1≤n≤20 0≤a[i,j]≤10710^7107 输入样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0输出样例
18[最短Hamilton路径] 等效旅行商问题不重不漏地经过每个点恰好一次(每个点都有过路费) 状态表示二进制枚举走或不走 f[i][j] : (二进制表示i的走法)经过i, 倒数第二个点为j的集合 起点和终点固定,中间过程考虑: 1.哪些点被用过 2.目前到哪个点 #include cstring
#include iostream
#include algorithmusing namespace std;const int N 20, M 1 N;int n;
int w[N][N];//费用 【邻接矩阵】
int f[M][N];//二进制表示的第i选法 到达第j个点的最小费用int main()
{cin n; for (int i 0; i n; i )for (int j 0; j n; j )cin w[i][j];//相当于有向图【邻接矩阵】memset(f, 0x3f, sizeof f); //求min, 初始化INFf[1][0] 0; //起点费用0【边界】 for (int i 0; i 1 n; i ) //枚举所有选法for (int j 0; j n; j ) //枚举倒数第二个点if (i j 1) 能走到j才有意义【否则剪枝】for (int k 0; k n; k ) //过程枚举起点0-k的最短距离if(i - (1 j) k 1) //【最后到j则从起点走到点k的路径不能经过点j】(取0-k中不经过j的状态:减去第j位的1) f[i][j] min(f[i][j] , f[i - (1 j)][k] w[k][j]); //取0-k中不经过j的状态更新//k视为倒数第二个点 [0 -- k k -- j] 费用f[状态][k] w[k][j]//,-等算术优先级大于 ,等位运算符【不清楚时按逻辑加小括号就行】cout f[(1 n) - 1][n - 1]; //最终状态[遍历完所有情况(0~2^n-1)][落到终点]return 0;
}day7
没有上司的舞会 - 树形DP
给定一张 n 个点的带权无向图点从 0∼n−1 标号求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式 第一行输入整数 n。
接下来 n 行每行 n 个整数其中第 i 行第 j 个整数表示点 i 到 j 的距离记为 a[i,j]。
对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x] 并且 a[x,y]a[y,z]≥a[x,z]。
输出格式 输出一个整数表示最短 Hamilton 路径的长度。
数据范围 1≤n≤20 0≤a[i,j]≤10710^7107 输入样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0输出样例
18经典树形DP - 类似状态机 邻接矩阵存边 题意 高兴度不与直接上司匹配 若选取匹配的两点没有直接连线,加两点的高兴度 即非父子节点【选取没有边相连的两点,加上点(员工)的高兴度】 集合划分 选根 / 不选根 状态u根(当前) s子节点 转移条件1表示选, 0表示不选 f[u][0] max(f[s][1], f[s][1]); **不选根 ** 可以选子节点选或不选都行 f[u][1] f[s][0]; 选根 不能选子节点
关键词最大独立集问题(还没学过)
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 6010;int n;
int h[N], e[N], ne[N], idx;
int happy[N]; //高兴度 可以简写为w[]
int f[N][2];
bool has_fa[N]; //【判断当前节点是否有父节点找根,没有父节点则为根】 (has_father) flagvoid add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}
//树形DP
void dfs(int u)
{f[u][1] happy[u]; //选择当前节点u, 加上自身的高兴度 [过程初始化]for (int i h[u]; ~i; i ne[i]) //遍历i的出边 i - e[i] {int j e[i]; //对应邻接点 dfs(j); //邻接点先全部初始化,加上自身高兴度//状态机f[u][1] f[j][0]; f[u][0] max(f[j][0], f[j][1]);}
}int main()
{scanf(%d, n);for (int i 1; i n; i ) scanf(%d, happy[i]); //高兴度 - 类比w[]权值memset(h, -1, sizeof h); //头结点初始化for (int i 0; i n - 1; i ) //读入n-1条有向边{int a, b;scanf(%d%d, a, b);add(b, a); has_fa[a] true; //b - a : a有父节点b(直接上司)}int root 1;//找根节点【根节点没有父节点】while (has_fa[root]) root ; dfs(root); //根节点为起点 输入起点根root 【状态机dfs-树形DP】 返回结果printf(%d\n, max(f[root][0], f[root][1])); //集合划分两种ans max(选根的高兴度和, 不选根的高兴度和)return 0;
}
