子希

算法设计与分析题库

ACM动态规划(4) ACM花里胡哨(1) c++(4) Dijkstra(5) javafx开发(1) java学习(1) oj几何(1) oj贪心(7) oj递归(5) stl练习题(6) 动态规划(2) 单调栈(4) 图论最小生成树(6) 图论-网络流(1) 图论最短路(8) 图论（杂）(5) 字典树(2) 字符串(8) 并查集(14) 思维题(23) 数据结构实现(2) 数据结构实验(2) 数论(1) 暴力(1) 暴力搜索(26) 有趣的数学题(1) 未归档(2) 树状数组(6) 模拟(3) 每日一题(1) 离散数学实验(5) 线段树(10) 网络比赛(6) 题解(43)

/ 注册

全部文章 / 算法设计与分析题库（共15篇）

FatMouse's Speed(DP+LIS变种)

题意：给你n个二元组(u,v)，要你求最长的u是递增，v是递减的子序列。思路：这个题乍一看不就是个最长上升子序列吗？然后满足一个约束v是递减的求不就行了？思路确实是这样，不过需要预处一下按u递增v递减排序(因为满足约束并且可以往回找)，这样可以把所有的子序列全部找出来，如果不预处理是找不出来...

2020-05-21

0 522

Human Gene Functions(DP+LCS变种)

题意：给你两个序列，序列的取值是(A,G,T,C)，并且给出一个他们之间的对应价值矩阵现在问题是，给你两个序列，你可以通过增加在字符串中间增加空格，最后要你求增加空格后的最大价值。思路：可以增加空格，那么一个简单的思想是通过增加空格使得字母匹配数最大化，这样就可以获得最大价值。那么难免会出现不...

2020-05-21

0 553

Fast Food(DP)

题意：给你n个饭店在横坐标轴上的位置，要你在这些饭店旁边建立k个仓库，使得所有饭店到最近的仓库距离之和最短，要你输出这个值。思路：这个题可以认为是管道问题的扩展版本，也可以认为是矩阵链乘的变种。定义dp[ i ] [ j ]:表示一共i个仓库在[1, j] 这些饭店的最短距离和转移方程：d...

2020-05-21

0 475

P1106删除问题(单调栈)

思路：单调栈维护一个递增序列，需要处理一些小细节，比说前导0等等，具体思路写在代码上了。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; char s[maxn]; void s...

2020-05-21

0 479

实验4，5

代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; int a[1010]; bool vis[maxn]; int path[maxn]; int k,m; stack<cha...

2020-05-21

0 422