日常吐槽：关于DP，有一种莫名的恐惧...maybe源于与mtw大佬与quantum11大佬，初中时抬老师爬楼梯的经历。。。 言归正传： 编辑距离 【题目描述】 设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2、插入一个字符； 3、将一个字符改为另一个字符。 对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。 【输入】 第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。 【输出】 只有一个正整数，为最少字符操作次数。 【输入样例】 sfdqxbw gfdgw 【输出...

原题链接__戳我噢 【思路】  （区间）DP F[I][J]表示前i本书分给j个人用的最短时间 由于每一次j的状态由比j小的状态得出，所以要先枚举j，然后枚举i，接着枚举上一次抄书的人是谁  我觉得，难点在于输出 具体见代码 压行压到手抽筋 #include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int read(){ char chr=getchar();int f=1,ans=0; while(!isdigit(chr)) {if(chr=='-'...

先讲一下：dalao @lisuier 发布的前一篇题解严格来讲是有错误的 比如下一组数据： 1 3 1 10 1 4 7 10 显然答案是3，然而用lisuier dalao的程序做出来的答案是2（后面会讲错误原因） 简单看出这道题用线段树可解 so 我们用离散化+权值线段树（戳这里详解） 实际上是安利自己博客 思路：建一棵空数，然后把某一区间的颜色更新为读入的颜色； WA,SO EASY OK 那我们先建一棵(10^7*4)的空树 然后 空间就炸了 正经的处理方法 对区间端点进行离散化 接下来 引用一下的 @lisuier 的话  离散化，如下面的例子，因为单位1是一个单位长度，将下面的 ...

【思路分析】  比赛的时候想到了用二分+贪心，二分的部分与贪心的部分也写对了，但是由于数据范围未看没有开long long，且二分左端点赋值过小导致WA掉 正解：二分+贪心 二分代码的长度，贪心判断能否达到，算法上没什么好说的，主要是细节处理上  关于细节处理：  开long long 右端点数据可以开的尽量大一点 输出-1的点要特别小心  代码： #include<cstdio> #include<cmath> #include<cctype> #include<iostream> #include<cstring> #includ...

【思路分析】  比赛的时候想到了用我确实也想到了树形DP，但是状态没有确定对，连样例都没有过 PS:这是第二道发现还可以用状态作为答案最后输出的题目 正解：树形DP（背包） 按照读进来的数据，我们先建一棵树 像这样(这里用vector存图)  for(int i=1;i<=n;++i){ int x=read(),y=read(); a[i]=x; v[y].push_back(i);//从父节点建一条边连向子节点 } 然后就是DP的过程 （本人见到的树形DP题目比较少，但是做到过相关的题目似乎都是想这样子的） void dfs(int x){ *********************...

貌似和石子合并差不多  可能是我见的题太少了，所以都差不多  OK  算法分析 首先不难看出这是一道区间DP，那么，按照本蒟蒻的意思  区间DP==三个循环 for(int len=2;len<=n;len++) for(int l=1;l+len-1<=n;l++） { int r=l+len-1; for(int k=l;k<=r;k++) 状态转移方程； }  接下来就是推方程的事情了  设f[i][j]为释放掉i~j号囚犯的最小花费，那么,容易得出 f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+一个数) 方程前半部分很好想，某个要释放...