题目链接 https://leetcode-cn.com/problems/minimum-window-substring/submissions/ 解题思路 大佬讲解思路不难理解，真正难的是实现和代码理解。 AC代码 class Solution { public: string minWindow(string s, string t) { string ans; map<char,int> ttt; int n=s.size(),m=t.si***len=0x3f3f3f3f,cnt=0; s='.'...

题目链接 https://ac.nowcoder.com/acm/contest/7604/B 解题思路 大致思路：首先明白往回跳是没有意义的。因为本题规定在某一位置能跳到的是一段连续的区间，可能存在往回跳的那个题，题目要求是从某个位置只能跳到某距离远的位置，对应的落脚点是零散的点，要与本题区别开来。正因为我们能跳一个区间的所有位置，所以我们根本不用担心一直往前跳能不能到达终点，它是必然可以啊。大致贪心思路就有了，在不使用法术的前提下，尽可能往前跳，跳的越远越好。完了，到了某点了，从前面任何一个位置以任何一种方式都没法跳到这个位置了，完了完了！唉，看来我们必须要使用魔法了。假设不使用魔法能跳到...

博客破百祭！！！ 题目链接 https://www.luogu.com.cn/problem/P1063 解题思路 一道十分类似的题成环已经不是难点了吧，化环为链。与上面那个题不同的是这个题两个数也可以操作，因为是俩珠子，形如珠子1(10,2) 珠子2(10,2)，最大的得分为10*2*10=200 > 2*10*2=40，显然上面那个题只能对至少三个珠子操作吧。dp的含义依旧是取走i，j之间的全部数，得到的最大值。本质上的区别在于本题可以取数取到只剩一个数，那我们把最长区间取到长度为n+1，最后输出长度为n+1的区间中的最大值，而且最小区间长度可以为2。当区间长度取到n+1的时候，a...

题目链接 http://poj.org/problem?id=1651 解题思路 比较简单，就是板子题稍微改了改转移方程。每次这种题，如果你想不出[i,k]和[k+1,j]与[i,j]的关系，你就想你要枚举的k的意义是什么，确定了k的意义之后就方便建立转移方程了。比如这个题，首先可以确定的是dp[i][j]表示[i,j]最少得分，最后留下左端点i和右端点j。直接去想[i,k]和[k+1,j]与[i,j]的关系，我想了许久都没想出来；换了换思路，思考k在枚举什么，k不就在枚举一个分界点，把区间[i,j]分成两部分，计算分成两部分后的最少得分。咋算，不难吧， 左边部分的最少得分+右边部分的最少得分...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4283 解题思路 dp[i][j]表示假如只有j-i+1个人，分别为i，i+1，……，j，这j-i+1个人进入小黑屋的愤怒值之和。对于区间[i,j]，每次只考虑第i个人的位置，那么他上场的顺序为第1个~第j-i+1个，设位置为k（k=i+上场顺序），这时，这个区间就被分为了两段， [i+1,k]和[k+1,j]。如何转移呢？让第i个人去第k个位置，也就是第（k-i+1）个上场，这样一来，就得把[i+1,k]所有的人前移一位，[k+1,j]无需动。转移方程：dp[i][j]=min{第i+1到第k个人...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2476 解题思路 大思路：题目要求字符串A转换到字符串B，我们先求空串（即与B串中任意同一位置的字符都不相等的字符串）转换到字符串B最少需要进行多少次操作（此情况为字符串A转换到字符串B的最坏情况，即每个位置对应字符都不相同，但凡A中存在与B同位置字符相等，都不至于操作这么多次），再根据空串转换到B串的操作次数，算出A串转化到B串的操作次数。S1：空串转换到B串：本质上是求每一段区间的空串转换成对应区间的B串的最少操作次数，用dp[i][j]保存。这时候我们考虑，要是B串中能有相同的字符就好了，要是...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4745 题解转自 https://my.oschina.net/u/4402652/blog/3524396 题目大意 给n个环状的数，A、B两个兔子沿相反的方向走，每次走一步，要求两个兔子每次到达的数要相同，（限制在一圈的范围内），问兔子最远能走几步。 解题思路 首先，把环倍增改成链，接下来找符合题意的最大步数用dp[i][j]表示在区间[i,j]内，兔子能走的最大步数 初始化dp，预处理问题的子结构，如果a[i]==a[j] , dp[i][j]=dp[i+1][j-1]+2如果 a[i]!=...

题目链接 NYOJ好像没了，不知道哪里能测评 题目及大佬题解链接 https://www.cnblogs.com/mooncode/p/10989408.html 解题思路 代码1： dp[i][j]表示前i位数，由j个乘号得到的最大值转移方程： dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i] j<=k<i代码2： dp[i][j][k]表示i到j位数由k个乘号得到的最大值转移方程： dp[i][j][k]=max(dp[i][j][k],dp[i][t][k-1]*a[t+1][j] 未必AC的代码1 #include<bits/std...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4632 题目大意 给你一个长度为N（N≤1000）的字符串，你输出它所有的回文子序列的数量（对10007取模）。只要从字符串 s 中顺序地取出一些字符（不要求连续，可以是 s 本身，不能是空串），不改变他们的顺序的情况下，这个子序列是一个回文串，那么他就是一个 s 的回文子序列。【输入格式】首先是一个数T（T≤50），表示测试用例的数量。接下来T行，每行包含一个字符串。【输出格式】对于每一个字符串，你需要输出它的回文子序列数量（由于数据量可能会比较大，所以结果需要对10007取模）。【样例输入】4a...

题目链接 http://poj.org/problem?id=2955 题目大意 我们定义一个字符串序列为“规则的括号序列”当且仅当它满足如下条件：1、空字符串是规则的括号序列；2、如果字符串 s 是一个规则的括号序列，那么 (s) 和 [s] 也是规则的括号序列；3、如果字符串 a 和 b 都是规则的括号序列，那么 ab 也是规则的括号序列；4、除此之外的字符串都不能称为规则的括号序列。举个例子，下面的这些字符串都是规则的括号序列：(), [], (()), ()[], ()[()]与此同时，下面的这些字符串都不是规则的括号序列：(, ], )(, ([)], ([(]给你一个字符串 a1a...

题目链接 https://www.luogu.com.cn/problem/P1880 普通dp题解链接 https://blog.nowcoder.net/n/420fe9ffda304281ad58f7abc03fb107 四边形不等式优化 很显然，直接区间dp板子搞上的时间复杂度为n^3，n到1000就TLE了。通过四边形不等式优化可以将时间复杂度降至n^2。我不会证明，能背过结论就不错了，WTCL。结论：记住吧我还是求最小值可以使用四边形不等式优化，但是求最大值不行，因为求最大值不满足某些条件。但是最大值的最优决策要么是k=i，要么是k=j-1，所以一个max(dp[i][i]+dp[...

题目链接 https://www.luogu.com.cn/problem/P1880 解题思路 区间dp+处理环。区间dp：，是因为你得从区间的长度入手，先把全部区间长度为1的得分算出来，才能算区间长度为2的，以此类推（应该可以记忆化）处理环：可以通过取模的方式处理，但那样过于繁琐。因此，我们直接再复制一段区间，这样就很像构成了个环。为什么这么处理就行？环和线唯一区别就在于线首和线尾元素不相邻，没法合并，把线扩大到两倍，就可以实现原线首与原线尾相邻。比如 1 2 3 4，1和4不相邻，通过翻倍 1 2 3 4 1 2 3 4，1与4可以相邻。同时应该注意到，我们最后要取长度为n的区间，如果取...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6556 题目大意 题目给了三个地方，后面的数表示与标准时间的差值。你要输入一个时间，俩地点，代表第一个地点的时间，求第二个地点此时的时间。 解题思路 直接懵了，因为我对12小时的闹钟真的是一直没搞明白过，有时候想定中午12点的闹钟，直接定成了凌晨，最后起晚了。所以，我们先说一下12小时的时钟， 12:00 AM 对应我们所谓的半夜零点； 1:00 AM 对应凌晨1点； 2:00 AM 对应凌晨2点； 3:00 AM 对应凌晨3点 …… 11:00 AM 对应上午11点 12:00 PM 对应中午12...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6555 解题思路 打表找规律，我也不知道大佬是为啥能知道有规律，而且还能秒的。Orz！真想吐槽一下题目表达，真想吐槽一下我的垃圾英语。 AC代码 #include<bits/stdc++.h> #define sc(x) scanf("%d",&x) #define pr(x) printf("%d",x) using namespace std; int n,x; int main(){ sc(n); for(int i=...