coin change 首先考虑没有限制的情况 当硬币被限制数量，需要加入对硬币情况的考虑 所以设dp[][] 记录凑齐x的种类 代码如下 #include iostream using namespace std; int main(){ int dp[251][101]={0},ans[251]={0}; int type[5]={1,5,10,25,50},x,i,j,k; dp[0][0]=1;...

2020-02-09 16:01:04

Longest Ordered Subsequence 这个嘛，我觉得是m[i]=max(m[0~i-1])+1;完了复杂度是O(n^2/2); 书上开了一个辅助数组d[]，就很nice，思想是如果m[i]d[最后一个],辣么直接添加进来， 如果m[i]d[最后一个]，就让它替换掉d[]中第一个比它大的，毕竟比它大的在前面，发展显然...

2020-02-09 16:00:56

common subsequence 求公共最长子序列数目，这种类型不用多想，dp就完了（自我感觉最简单的dp） 首先确定状态，两串字符串比较，所以用二维的dp[i][j] 然后转移方程，当str1[i]=str2[j]时，由两字符串同时加一得到，dp[i][j]=dp[i-1][j-1]+1; 当str1[i]!=str2[j]时，dp...

2020-02-09 16:00:50

pearls 这道题用dp解刚刚好（求最优解） 首先确定状态：dp[x],一个未知变量 状态转移方程：dp[x]=min(dp[x],dp[x-i]+(num[i~x]+10)*price[x]); 显然对于每个x都满足这个方程 初始化dp[0]=0,dp[x]=MAX; 从1到x用方程逐个求解 接下来放代码： #include iostream using na...

2020-02-09 16:00:43

Asteroids!_poj2225 这是一个立方体的空间的路径搜索问题，若可达输出步数，不可达输出NO ROUTE 一道课后题 输入的话我是按字符输入这个空间的 然后普通的bfs，一个方向数组，一个空间数组（因为只用一次，懒的再开一个，反正标记了，就是不能走的意思）引入某大佬的函...

2020-02-09 16:00:36

图论初步蒟蒻专属文章 前言 ： 图论乃noip之重要知识点，但有点难理解 本人因此吃过不少亏 因为本人实在太弱，所以此篇乃正宗 蒟蒻专属文章 正文：（本文仅介绍图论中的重点、难点，其余部分略将或不讲） 图一般来说有二种存储方法：邻接矩阵和邻接表 邻接矩阵 ： 存储...

2020-02-08 16:01:06

AtCoder agc007_d Shik and Game 洛谷题目页面传送门 AtCoder题目页面传送门 有 \(1\) 根数轴，Shik初始在位置 \(0\) 。数轴上有 \(n\) 只小熊，第 \(i\) 只在位置 \(a_i\) 。Shik每秒可以向左移动 \(1\) 个单位长度、原地不动或向右移动 \(1\) 个单位长度。Shik第 \(1...

2020-02-08 16:00:56

#《Essential C++》读书笔记# 第四章 基于对象的编程风格 基础知识 Class的定义由两部分组成：class的声明，以及紧接在声明之后的主体。主体部分由一对大括号括住，并以分号结尾。主体内的两个关键字public和private，用来标示每个块的“member访问权限”。Public memb...

2020-02-08 16:00:36

单调队列 1.单调队列简介： 单调队列是一种数据结构，类似如单调栈，但里面的元素必须在一个区间内，如果过时就要出队。所以，单调队列可以在两端进行出队，但只能再队尾入队。按此性质，传统的队列已无法满足需求，需要使用双端队列，再C++的STL里，双端队列定义在deq...

2020-02-07 16:01:45

c++中比较好用的“黑科技” 切入正题，上黑科技 一、黑科技函数 （常用的我就不写了，例如sort函数） 1.next_permutation(a+1,a+1+n) a[1-n]全排列 2.reverse(a+1,a+1+n) 将a[1-n]的数翻转过来 3.*max_element(a+1,a+1+n) 找出a[1-n]数字最大值(*是因为这个函数是一个...

2020-02-07 16:01:14