south_king

dp

bzoj(7) hdu(1) kmp算法(1) NEW(1) python(1) spfa(12) tarjan(5) vijos(2) 二分(1) 二分图(1) 二叉树(1) 回忆(1) 搜索(2) 数论(7) 最小生成树(2) 期望dp(1) 未归档(8) 树形dp(3) 树状数组(1) 模拟(2) 模拟退火(2) 模板(14) 水题(14) 洛谷(17) 状压d(2) 考试(13) 贪心(2)

/ 注册

全部文章 / dp （共7篇）

动态规划最长上升子序列 nlogn

题目描述 LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？给出一个长度为N整数序列，请求出它的包含第K个元素的最长上升子序列。例如：对于长度为6的序列<2,7,3,4,8,5>，它的最长上升子序列为<2,3,4,5>...

2021-05-28

0 441

NOIP 冲刺之矩阵DP

//今天早上这篇博客呢，名字是我瞎yy出来的大概就是有这样一种题：给你一个n*n的矩阵，有些点有权值，然后让你找出两条路径，让权值之和最大（取走后的方格中将变为数字0）我们设这样一种四维的数组 int f[55][55][55][55];//第一个人走到i,j第二个人走到k,l最优值 ...

2021-05-28

0 355

NOIP 模拟10.20

T1:【bzoj2748】[HAOI2012]音量调节 Description 一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选...

2021-05-28

0 458

洛谷P3842 [TJOI2007]线段

本来想先写图论专题的，但这题蹦出来了，就先写她了啦啦啦啦~ 题目链接https://www.luogu.org/problem/P3842（洛谷真是越改越丑了）题目描述在一个 n*n 的平面上，在每一行中有一条线段，第 i 行的线段的左端点是(i, L(i))，右端点是(i, R(i))，其中...

2021-05-28

0 360

洛谷P1005 矩阵取数游戏

题目描述帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n×mn \times mn×m的矩阵，矩阵中的每个元素ai,ja_{i,j}ai,j均为非负整数。游戏规则如下：每次取数时须从每行各取走一个元素，共nnn个。经过mmm次后取完矩阵内所有元素；每次取走的各个元素只能是该元素所在行的行首或行尾...

2021-05-28

0 431

洛谷P2034 选择数字

题目描述给定一行n个非负整数a[1]…a[n]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。输入格式第一行两个整数n，k 以下n行，每行一个整数表示a[i]。输出格式输出一个值表示答案。一个小dp 我们设f[i]为不选i时候的最...

2021-05-28

0 350

洛谷 P5424 [USACO19OPEN]Snakes G

传送门我自关山点酒，千秋皆入喉题目描述：略思路：这个东西明显就是一个区间的dp,f[i][j]代表抓到第i条蛇，用了j次修改的最优值。（这个题有个坑啊，观察样例可以发现第一次调整网的大小是不算在k次操作里面的呜呜呜。）下面考虑怎么转移：我们设g[i][j]代表只用一张网抓[i][j]的...

2021-05-28

0 482