1 爱吃老谈酸菜牛肉面的DV

尚未进行身份认证

我爱学习,学习使我快乐

等级
TA的排名 3w+

51nod:1051 最大子矩阵和

描述一个M*N的矩阵,找到此矩阵的一个子矩阵,并且这个子矩阵的元素的和是最大的,输出这个最大的值。例如:3*3的矩阵:-13-12-13-312和最大的子矩阵是:3-1-1312输入第1行:M和N,中间用空格隔开(2<=M,N<=500)。第2-N+1行:矩阵中的元素,每行M个数,中间用空格隔开。(-10^9<=M[i...

2019-10-17 17:37:02

CodeForces - 284D:(记忆化搜索)

DiscriptionFarmerJohnhasjustgiventhecowsaprogramtoplaywith!Theprogramcontainstwointegervariables,xandy,andperformsthefollowingoperationsonasequencea1, a2, …, anofpositi...

2019-10-17 00:14:48

2019年10月16日训练日记

今天晚上依然是做了一套题,跟上一套题一样的,水题上一场都做过,我们很快就出了,然后在考虑那几道难题,有一道是个深搜题,看了好久也没做出来,然后又去做了另一道,是道记忆化搜索的问题,这道题我们之前用暴力模拟过,但是卡超时过不了,后来才知道要用到记忆化搜索。自己想了好一会,还是没做出来,看了题解才明白。最近的话已经开始做51nod动态规划部分的问题了,感觉我做的有点太慢了,老师卡各种细节问题,还有对...

2019-10-17 00:04:57

1086 背包问题 V2(二进制优化多重背包)

描述有N种物品,每种物品的数量为C1,C2…Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2…Wn(Wi为整数),与之相对应的价值为P1,P2…Pn(Pi为整数)。求背包能够容纳的最大价值。输入第1行,2个整数,N和W中间用空格隔开。N为物品的种类,W为背包的容量。(1<=N<=100,1<=W<=50000)第2-N+1...

2019-10-15 19:24:17

2019年10月13日训练日记

前两天老是发了个题库,开始刷题了,总感觉有种莫名的兴奋。这周末家里有事,回了趟家,白天没怎么有时间去做题,晚上做了几道题,不多。今天在返程的火车上做题,一直做到了电脑没电,感觉很充实。做题过题的过程本身就很快乐,让我感到身心愉悦。最近也是从简单的DP开始入手,推导状态转移方程都比较容易,有的可以直接套板子,但是干最最近有点智障,老是卡一些小错误,比如说没用longlong,数组开小了,没有m...

2019-10-13 23:55:45

51nod1134 最长递增子序列(基础dp+优化)

描述:给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)例如:516824510,最长递增子序列是124510。输入第1行:1个数N,N为序列的长度(2<=N<=50000)第2-N+1行:每行1个数,对应序列的元素(-10^9<=S[i]<=10^9)输出输出最长递增子序列...

2019-10-13 14:47:59

fill()和fill_n()函数的使用方法

一、函数的功能在头文件<cstring>中1.fill()函数,给定数组的首地址和末地址,以及要赋得值value,实现对数组的整体赋值value。2.fill_n()函数给定赋值得起点和要赋值得数量count,以及要赋的value值,实现从起点后给数组赋count个value值。注意:不能在空容器调用fill_n()一、使用格式1.fill():一维数组:fill(a,a...

2019-10-13 11:21:20

2019年10月9日训练日记

今天晚上依旧是打了比赛,出了两道题,两道水题,然后网站就莫名其妙的崩了,还剩不到一个小时的时候才好,又去看了下E题,没做出来。最近也是看了一些DP的博客,前一阵在看状压DP,最近在看区间DP了,状压DP使用二进制数记录状态,然后进行状态转移的。最近看的区间DP我觉得就是用状态转移方程来实现DFS或者是递归的操作,就是求解一个区间的最值,然后将区间不断下分,知道不能再划分为止,就能求解出区间的最值...

2019-10-09 22:11:08

约瑟夫环问题(循环链表实现)

描述约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。输入813(n=8k=1m=3)输出7(剩下的那个)样例输入831样例输出7AC代码#include<bits/stdc...

2019-10-08 08:48:27

有序双向链表的实现

双向链表要求建立当前节点和他前驱和后继的关系,切必须保证有序。包含插入、删除、排序、遍历输出等函数。详见代码:#include<iostream>usingnamespacestd;template<classT>structNode{Tdata;Node<T>*rlink,*llink;};template...

2019-10-08 08:46:44

2019年10月6日训练日记

最近依旧是看dp,之前状压dp看了好多,弄明白了基本的思路的原理,但是还没太掌握,可能得再需要一段时间去感悟。最近看了一些区间dp的题,区间dp我觉得很多都是使用了递归的思想,把一个完整的区间的一个比较庞大的问题转化成小规模的区间的问题,一步步划分下去,知道不能划分位置,然后从小问题的结果回溯回大问题就是题目的答案,就像是体格递归的过程,将问题细化下去的做法比较好想,但是我最近看的几个区间dp的题...

2019-10-07 01:31:52

2019年10月2日训练日记

最近一直再看状态压缩DP。我觉得状压DP就是利用二进制记录状态,利用位运算进行状态转移的一个完全暴力的算法。最近看题总是看到一种题型就是给定一个n行m列的格子,往格子上放东西,问最多可以放多少,或者是在某个位置放一个,然后其上下左右都不能再放,或者是放一个特定形状的格子,这一类题都可以考虑使用状压DP求解,每一行用一个二进制数记录状态,每一位的0,1记录取或不取,拿或没拿,走过或没走过,可以用它...

2019-10-02 22:02:32

字典树(实现前缀匹配的问题)

举个例子,给你n个单词,每个单词的长度最大不超过len,给的顶一个长为length的长字符串,问这个字符串的前缀里包含多少个所给的单词。先分析这道题,需要建立一个字典树将所有的单词都放到一个树里(可以看成一个26叉树,每一层都是字母a~z),然后用长文本去暴力匹配这个树,记录个数。

2019-09-30 23:51:56

2019年9月29日训练日记

这几天依旧是看看的DP,感觉自己的效率的确是有些低了,经常是看东西看不进去,或者是有看不懂的地方。最近也反思了一下,感觉有的博客看的太草了,只记得一个大概,具体内容都记不住,,看过的知识也很容易忘,一个题看懂了过几天又就忘了。自己想了一下原因,可能是看代码看的不够细,有的代码太长了,就会不太想看,然后就草草的过去了,过几天还是啥也不会,而且只看别人的思路和代码有时候明明看会了,但是自己实现就还是会...

2019-09-29 22:04:10

2019年秦皇岛J题:MUV LUV EXTRA(KMP后缀数组)

ProblemDescription鉴纯夏是一名成绩不太好的高中生。一天她在数学考试中碰到了一道求某条线段长度的问题。因为她并不会做这道题,所以她准确地作图后用尺子量出了这条线段的长度。不幸的是,答案在10进制下为一个无限小数,纯夏只量出了这个无限小数在10进制表示下的前若干位。纯夏猜测问题的答案为一个有理数,所以答案为一个无限循环小数,如13=0.333⋯,3635=1.028571428...

2019-09-28 17:08:29

2019年秦皇岛区域赛I题:Invoker(动态规划)

ProblemDescription在dota2中有一个叫做祈求者(Invoker)的英雄,在游戏中他有三个基础技能:冰(Quas),雷(Wex),火(Exort),每施展一个技能就可以获得相应属性的一个法球(element)。但是祈求者同时最多只能有三个法球,即如果他在有三个法球的状态下又使用了某个法球技能,那么他会获得该法球,并失去之前三个法球中最先获得的一个。不难得出,祈求者身上...

2019-09-28 16:45:59

2019年9月25日训练日记

今天我们竟然爆零了,队友在做A那道数论题,我就一直在做C那道题,模拟C的过程,一直超时,一直超时,测评机好像炸了,判断一发二三十分钟,队友那道A也被卡了,B题好像是所有题中偏简单的一道题,但是竟然都没读懂题意,交了两发,题意都没读对。我太菜了。最近依旧在看DP,一般都是晚上看,或者上水课看,老师老是下来转,看的我很不安心,提心吊胆的。之前有几天落下了几篇博客,这两天都补回来了,依旧是是在很迷的阶...

2019-09-25 22:20:21

单链表的实现

带头节点的单链表的实现,被卡了好久的RuntimeError,指针没有控制好。#include<bits/stdc++.h>usingnamespacestd;template<classT>structNode{Tdata;Node*next;};template<classT>classLinklis...

2019-09-24 20:40:55

题目整理(DP)

1.AcWing272:最长公共上升子序列(经典DP)题意:就是求解两个字符串的最大上升公共子序列。 思路:需要结合最大上升子序列和最长公共自序里啊两个题来进行求解。 博客链接:https://blog.csdn.net/weixin_43460224/article/details/1011755402.hdoj2084数塔问题(经典DP)题意:给定一个数塔,求解从顶部走到底部...

2019-09-22 23:19:43

AcWing272:最长公共上升子序列(经典DP)

最近开始刷DP题,先从简单的开始吧。题目链接:https://www.acwing.com/problem/content/274/题目描述:熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。小沐沐说,对于两个数列A和B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这...

2019-09-22 22:26:09

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。