荒野孤鹰

好久没写博客了，看了下上一篇博客还是八月份的最后一天写的，然后就因为阿里拥抱变化，忙着找工作去了；9月份找到工作，10月份又胡思乱想了一个月，但其实都是没必要的，应该明白胡思乱想解决不了任何问题的，实在得不到的又何必强求，顺其自然吧。加油吧，少年！！！题目链接：点击进入 下午训练的时候这道题想了好几个小时还是完全没有思路，但是静下心来还是可以看到一些规律的。首先w=i+1的情况和w=i时的情况是有

如果我们将每一种优惠方案看成一种物品，那么这个问题就可以转换成背包问题，我们可以定义ｄｐ[a1][a2][a3][a4][a5]表示购买第一到第五中物品ａi个时的最小代价，然后转移方程类似于完全背包ｄｐ[a1][a2][a3][a4][a5]=min(dp[a1-st[i].num[a1]][a2-st[i].num[a2]…[a5-st[i].num[a5])；但是这样还不够，因为根据题目要求其实

如果我们可以求出两个人n张牌取k张的所有情况,问题就会变成一个简单的排列问题:A获胜的概率=A k张牌比B k张牌大的情况/总情况.然后我们可以用dp处理出n张牌中取k张牌的所有情况,dp[i][j][k]表示前i张牌中取j张牌构成k点的情况数, 状态转移:dp[i][j][k]=dp[i-1][j][k]+k>=a[i]?dp[i-1][j-1][k-a[i]]:0; 然后就是在计算概率时因为

开始的时候暴力了一次,但是在第10个点就超时了.后面才知道这个题实际上是一个组合数的题目.在每个位置我们可以选择放0或者1,并且我们可以统计出每种放法后面数的排列数,然后我们可以决定放0或放1,继续这个过程直到最后. 所以重点是计算出dp[i][j],表示i位中至多有j位1.对这个我们可以采用dp的方法来求dp[i][j]=dp[i-1][j]+dp[i-1][j-1]; 也可以使用组合数来求d

因为要求连续，所以我们必须顺序的判断每一枚邮票的面值，考虑已经得到前i个可能的面值，那么我们怎么判断第i+1个面值可不可得到？我们可以知道i+1面值的这枚邮编，可以由0—i面值中的邮票加上某一个可取的面值得到，但是由题目的限制，我们要保证构成构成i+1面值邮票的cent数必须少于k。 我们定义dp[i]表示构成面值为i的邮票所需的最小的cent数，然后dp[i]=min(dp[i-a[j]]+1)

其实还是穷举子集类的dp,一般这种dp我们只需要用一个一维的滚动数组就可以了,但是这个题目状态转移的时候不但可能向后还有可能向前,所以这次得用二维数组. 状态方程 dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]],分别表示第i个数不取和第i个数取情况下状态.代码如下:#include<iostream>#include<cstdio>#include<cstring>

就是一简单的完全背包问题，秒杀。代码如下：/*ID:15674811LANG:C++PROG:inflate*/#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 11000int main(){ freopen("inflate.in","r",stdin);

完全背包的简单变形，秒杀。代码如下：/*ID:15674811LANG:C++PROG:money*/#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<fstream>using namespace std;int main(){ o

很久没做dp了，然后开始看到这题目都不知道该怎么下手了；其实这是一道dp的典型题，每次都可以有多种选择但是不到最后是不知道最优解的。 令dp[i]表示以i为起点的最长前缀，然后dp[i]=max(dp[i+len[j]]+len[j]) 当然i+len[j]要小于原字符串的长度。代码如下：/*ID:15674811LANG:C++PROG:prefix*/#include<iostrea

令dp[i][j]表示i个节点构成高度不大于j的树的方法数。如果我们将给定的树去掉根节点，那么这棵树就可以分成独立的左右两棵子树，然后如果左子树具有a中形态，右子树具有b中形态，那么这棵树总共有a*b种形态。 所以我们得到状态转移方程dp[i][j]=dp[k][j-1]*dp[i-k-1][j-1].其中k可以看成是在穷举左子树中含有的节点数为k个。边界条件是dp[1][1,k]=1;代码如下：

先将立方体按重量从大到小排序，然后就转成了类似于最长上升子序列的问题；定义状态dp[i][j]表示以第i个立方体的第j面作为顶面的最大高度则dp[i][j]=max(dp[k][d]+1;1注意为了方便后面的状态判定，我们在输入的时候要使得相对的面的坐标和为一个常数5.代码如下：#include#include#includeusing namespace

定义dp[i][j]表示第i天到达城市j的最小花费则  dp[i][j]=min(dp[i-1][next(j)]+cost(next(j),j))当然不是每天都会有飞机的，需要判断一下代码如下：#include#include#includeusing namespace std;int T[15][15],a[15][15][35];int dp

第一道概率期望dp:)其实和一般的dp也差不多，只要状态选好就行了。定义dp[i][j]表示还剩i只白老鼠j只黑老鼠时候公主赢得概率。则：1.公主选白老鼠，直接赢，概率：i/(i+j)        2.公主选黑老鼠             1）龙选黑老鼠，逃走黑老鼠；概率：j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)           

二维的完全背包问题。令dp[i][j]表示当x=i,y=j时的最小代价；则：   dp[i][j]=min(dp[i][j],dp[i-wx[k]][j-wy[k]]+1);至于方程的实现则可以仿照一维的背包问题写。代码如下：#include#include#include#includeusing namespace std;int dp[33

二维dp,定义G[i][j]表示i,j为顶点的最大正方形边长.如果G[i][j]本身为1,则转移方程为:G[i][j]=min(G[i+1][j],G[i][j+1],G[i+1][j+1])+1.其实就是由其下方,右方,右下方的点确定它所能构成的最大正方形(在图上可以很清楚的发现这一点). 其实这道题也可以暴力枚举;我们枚举每个点作为正方形左上角顶点时可以得到的最大边长正方形,而边长为k的正方形

一道dp,其实我们只要求出第一个人的最大和.定义sum[i][j]表示区间i,j所有元素之和.dp[i][j]表示从面对区间i,j时先取所能得到的最大和. 状态转移方程: dp[i][j]=max(sum[i+1][j]+a[i]-dp[i+1][j],sum[i][j-1]+a[j]-dp[i][j-1]). 可以化简成: dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[

题目链接：点击进入 昨天晚上比赛的时候，我居然想着用dfs做这道题，果断超时了。其实因为城市的数量非常的小，n最大才12，所以我们是可以借助于二进制进行状态压缩的；定义dp[s][i]表示当前访问城市的情况为s时下一个访问城市为i时的最小油量，则转移方程为dp[s|(1<<(i-1))]=min(dp[s][j]+dis[i][j])，状态转移方程的意思就是从s中找到已经访问过的城市j，然后再从j

题目链接：点击进入 以前也碰到过这种类型的dp，感觉就是状态不好定义和转移；原来定义状态的时候总是认为dp[i][j]就应该由dp[i-1][j-1]转移而来，这样的话就会导致需要记忆前面i-1步的所有状态，然后就是转移方程没法写了。对于这道题，我们定义状态dp[i][j]表示前j个餐馆建立i个仓库时的最小代价，然后状态转移为dp[i][j]=dp[i-1][k-1]+cost[k][j],意思是

题目链接：点击进入 原来定义状态dp[n][n1][n5][n10]表示购买ｎ瓶可乐后剩余１,5,10分硬币ｎ1,n5,n10个时花费硬币数最小的数量．然后状态转移是：１.８个一分硬币购买第ｎ瓶可乐,t=dp[n-1][n1+8][n5][n10]＋８; 2.一个五分和３个１分,t=dp[n-1][n1+3][n5+1][n10]+4; 3.两个５分t=dp[n-1][n1][n5+2][n1

题目链接：点击进入 首先对于长度最短的情况是很容易确定的，只需要用两个字符串的长度和减去他们的最长公共子序列长度。然后比较麻烦的就是合乎要求的字符串的个数，其实我们也可以用类似于最长公共子序列的dp来求。 设dp[i][j]表示str1的前i个字符和str2的前j个字符所得到的满足要求的字符串，则如果str[i]==str[j]，则dp[i][j]+=dp[i-1][j-1]; 否则就要根据i，

题目链接:点击进入 刚看到这题目还以为又碰到水题了,结果写了个最长O(n^2)的代码交上去超时了,才发现n有250*250那么大.后面在网上找到了一个nlgn求最长上升子序列的方法,才过了.这个nlgn算法的主要思想是将最长公共子序列转成最长上升子序列,然后用最长上升子序列nlgn的算法求解.更具体的解释可以参看这篇博文:最长公共子序列(nlogn) 代码如下:#include<iostream>

题目链接: 点击进入 这个题n最大的时候只有8,但是直接暴力dfs的话还是会超时的,所以我们采用记忆化搜索的思路.要记忆化搜索就要找到一个合适的方法来表示当前的状态.对这个题恰好可以用一个n位的二进制表示,开始的时候都为1表示没有人配对;状态转移就是每次选择两个没配对的配对,并且将二进制数的对应位置0.代码如下:#include<iostream>#include<cstdio>#includ

题目链接：点击进入 最多只有16个点，如果不用状态压缩的话，最优子结构没法找到。所以我们进行状态压缩，用一个数表示当前的状态，对应二进制位为1表示该位置的树还未被砍掉，为0表示已被砍掉，初始状态为(1<#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 20#define

题目链接:点击进入 上次做了一个类似的,不过是每次只能取一个的.这次规定可以一次取多个了.定义状态dp[i][j]表示面对区间(i,j)时可以得到的最大分数,然后dp[i][j]=max(sum[i+k][j]-dp[i+k][j]+sum[i][i-k+1],sum[i][j-k]-dp[i][j-k]+sum[j-k+1][j]).综合一下就是dp[i][j]=sum[i][j]-min(dp

题目链接：点击进入 定义dp[i][j]表示将一个皇后放在第ｉ列第ｊ行有多少种放法．则转移方程dp[i][j]+=dp[i-1][k].如果flag[i]==’?’,1<=j<=n，否则j只能取一个值，而１＜＝ｋ<=j-2,j+2<=k<=n.代码如下：#include<iostream>#include<cstring>#include<cstdio>using namespace std

类似于背包,但是最后物品可以拆分.另外,因为要求第一次的选择,从后往前进行dp.代码如下:#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define INF 0x3f3f3f3ftypedef struct{ int cnt; int w[103],v[103];}P;P

题意:给定一个n,求n位数中有多少个数的前n/2位的和与后n/2位的和相等. 思路:题目保证n为偶数,我们定义dp[n/2][j]表示前n/2位数和为j的种类数,则答案为sum(dp[n/2][0–n/2*9]).接下来我们进行dp,定义dp[i][j]表示i位数和为j时的种类数,那么其实这个dp就是在10位数中选择i位,构成不同的和,易得转移方程dp[i][j]=sum(dp[i-1][j-k]

题意: 在一个w*h宽的矩形中有些位置有树有些位置没有,然后我们需要从中选一个s*t的矩形,使得里面含有的树最多. 思路: 我们将有树位置的值看成1,其它为0,然后成了选一个区域值最大.然后考虑这个问题的一维形式,在一维的情况下,我们很容易得到一个方案:先处理前缀和,然后就可以枚举区间端点的起点,O(1)时间计算区间和,然后取其中的最大值为答案. 这道题我们可以按同样的思路来做,先求出(1,1)

题目链接:点击进入 开始看到m和k都很小,就直接暴力了一发,结果T了.后面看到m只有6那么大,k又小于10,就觉得可以用记忆化搜索,状态我们就定为dp[n1][n2][n3][n4][n5][n6],表示n1–n6六种化学试剂的量,状态转移就时选两份试剂进行混合.代码如下:#include<iostream>#include<cstring>#include<cstdio>using nam

经典字符串区间dp，注意动态规划方程时按区间长度进行递推。代码：#include#include#includeusing namespace std;char str[100];long long dp[100][100];void solve(){ int len=strlen(str); memset(dp,0,sizeof(dp))

多重背包求最优解问题。代码如下：#include#include#includeusing namespace std;int V;long long sum[110000];int w[50];void Init(){ memset(sum,0,sizeof(sum)); sum[0]=1;}void solve(){

字符串区间dp。定义dp[i][j]表示将i--j之间的字符串变为回文串所需的最小步数当str[i]==str[j]时 dp[i][j]=dp[i+1][j-1];当str[i]!=str[j]时，dp[i][j]=min(dp[i+1][j-1],dp[i][j-1]+1,dp[i+1][j]+1)对于此状态转移方程，当然可以采用记忆化搜索实现，也可采用递推的形式实现;采用递

从一个点开始，如果始终只往右边和下边走，则如果能到达右下角距离必定是最小的，且无论走那条路线距离都是一样的。代码如下：#include#include#includeusing namespace std;char str[100];int G[1000][1000];int dp[1000][1000];int n,m;void input(){

经典的最长公共子序列问题。要注意的是题目中的输入会包含空格的情况，所以要用gets实现输入。代码如下：#include#include#includeusing namespace std;int dp[1100][1100];int main(){ char str1[1100],str2[1100]; int i,j; whi

开始的时候一直想不到一个合适的状态转移方程；后面想到可以分别求以中间那个数为终点和起点的最长上升子序列的长度，然后以这个数为中心数的Wavio Sequence的长度就是其中短的那个值*2-1的值；然后我们取所有数Wavio Sequence的最大长度作为答案。这个题目卡了n^2的求最长上升子序列的算法，必须用nlgn算法才能过。代码如下：#include

可以定义dp[i][j]表示第一个串的前i个字符中含有第二个串的前j个字符的总情况数；则：如dp[i][j]=dp[i-1][j]，如果str1[i]==str2[j]则dp[i][j]+=dp[i-1][j-1];初始时讲所有的dp[i][0]赋值为1，其他为0。然后这个题目需要用到大数，可以用C++重载运算符，或者是java的大数类；我用的是java，第一次用java的大数，感

背包类统计最优解个数问题代码如下：#include#include#includeusing namespace std; long long sum[50000];int main(){ double d; int w[]={0,5,10,20,50,100,200,500,1000,2000,5000,10000},i,j; me

题意：    给定一堆硬币，然后将他们分成两部分，使得两部分的差值最小;输出这个最小的差值。思路：   想了好久都没想到一个合适的状态转移方程。后面看了别人的题解后，才知道可以转成背包问题求解。我们将所有的硬币和的一半作为背包容量，然后将硬币的代价看成其本身的面值。然后背包中能装的最大容量就是其中一个人分得硬币数。代码如下：#include#inclu

题意：    其实就是把矩形嵌套扩大到了n维，但是规定这个n维的几何体是可以任意扭曲的。思路：   就是按照矩形嵌套问题的思路，不过判定是否可以嵌套的时候，我们直接都排一下序就判断了（因为是可以任意扭曲的）。还有就是需要打印出整个序列，这里可以借用小白书上的思路，递归进行打印。代码如下：#include#include#include#includeus

题意：   其实就是求两个序列的最长公共子序列。思路：  这个题目的输入是很坑爹的，如果把输入理解清楚后，这个题目就不难了。题目的输入表示的是该位置上的数放在哪个位置上，比如说输入是1,3,2,4其对应的序列应该是1,3,2,4;  下面给出2份代码，一份是经典的解法，一份是今天我写的把问题转成DAG图上的最长路求解的代码。代码如下：#include#in