Fragrantnumbers（dfs爆搜+区间dp）题意：给出一个以"1145141919"无限循环的字符串，可以在合适的位置添加'+','*'和'(',')'将其转换为表达式进行运算，给了一个n，问最少需要前几个字符来构成n?题解：(dfs)爆搜+区间dp:(dp[l][r])记录字符串(l)到(r)之间可以产生的...

选择    题解： 其实画一画很容易知道：偶数个的话，最多选(leftlfloorfrac{i}{2}ightfloor)；奇数个的话，可以选(leftlfloorfrac{i}{2}ightfloor)个也可以选(leftlfloorfrac{i}{2}ightflo...

JumpingHaybales  题意：从左上角到右下角，‘#’不能落脚，每次可以向下或者向右跳小于等于k的距离，问最小需要多少步到达右下角分析：设dp[i][j]表示到达点坐标点(i),(j)所需的最少步数，状态见代码AC_Code:1#include<bits/stdc++.h>2u...

【使用情况】：在状态比较多的情况下，同时状态只需要记录是或非，使用二进制将其压缩，从而达到缩减时间复杂度的效果。由于要使用二进制来表示状态，所以这类问题的数据范围会相对较小(left(nleq20左右ight))，时间复杂度经常含有O(2n).代替爆搜的常用方法【二进制基础】：若当前状态为s，对s有如下操作：（第i位是...

  AC_Code:1#include<iostream>2#include<cstdio>3#include<cstring>4#include<string>5#include<cmath>6#include<queue>7...

首先我们要清楚数位dp解决的是什么问题：求出在给定区间[A,B]内，符合条件f(i)的数i的个数。条件f(i)一般与数的大小无关，而与数的组成有关由于数是按位dp，数的大小对复杂度的影响很小这里我们使用记忆化搜索实现数位dp。本质上记搜其实就是dp，下文会重点介绍dp值的使用和记录一、记搜过程从起点向下搜索，到最底层得...

问题定义：对于给定序列a1,a2,a3……an寻找它的某个连续子段，使得其和最大。模板：1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintmaxn=110;5constintinf=0x3f3f3f3f;67intm...

MonkeyandBanana    AC_Code:1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5usingnamespace...

线性dp之序列问题【基本概念与性质】1.子序列：一个序列A＝a1,a2,……an中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。（例如：对序列｛1,3,5,4,2,6,8,7｝来说，序列｛3,4,8,7｝是它的一个子序列。）2.公共子序列：如果序列C既是序列A的子序...

求一个数列的最长上升序列　　动态规划法：O(n^2) 1//DP2intLIS(inta[],intn)3{4intDP[n];5intCnt=-1;6memset(DP,0,sizeof(DP));7for(inti=0;i<n;i++)8{9for(intj=0;j<i;j++)10{11if...

题目链接：here题目分析：放置哨兵无非两种情况，放或不放，我们可以用dp[i][1]来表示第i个结点放置哨兵,dp[i][0]来表示第i个结点不放置哨兵,我们可以从上往下，从左往右来遍历树，所以这就用到了树形DP的知识，我们很容易知道，如果父亲结点没放哨兵，那么子结点肯定要放置哨兵，如果父亲放置了哨兵，那么子结点可以...

题目链接：https://cn.vjudge.net/contest/317407#problem/A   题目理解：题意为有n个人要开一个PARTY，编号1到n，每个人都有一个欢乐值，并且每个人都有一个直接上司，为了让气氛更好，要求在这n个人中选一些人去参加PARTY，并且选出的这些人中...

前言：　　话说DP这种纯考思维的题目，总是让我很伤脑筋，一些特别简单的DP我都常常做不出来，所以革命从现在（2018-05-01）开始，努力多刷点DP的练习～。 1.顺序对齐(align)时间：2018-05-01Description　　考虑两个字符串右对齐的最佳解法。例如,有一个右对齐方案中字符串是AAD...

loidc来到了NOI的赛场上，他在那里看到了好多神犇。神犇们现在正排成一排在刷题。每个神犇都有一个能力值p[i]。loidc认为坐在附近的金牌爷能力参差不齐非常难受。于是loidc便想方设法对神犇们进行人道主义合并。loidc想把神犇的能力值排列成从左到右单调不减。他每次可以选择一个神犇，把他合并到两侧相邻的神犇上。...

第一次自己写树形DP的题，发个博客纪念`～某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，...