hdu2048 题目链接 题意:n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片，取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。 思路：错排。。。 复习了一下错排公式。。。d[n] = (n-1)*(d[n-1]+d[n-2]) （d[1]=0,d[2]=1） 然后求概率的时候。。惊讶得发现概率稳定在了36.79%（1/e）附近。。。 这是因为。。。错排还有一个公式：D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]. 求概率每次把n!除掉了。。剩下的。。其实就是e的泰勒展开，当x=-1时的值。 因为当n越大时。。这个概率越接近1/e 这道题 …

hdu 2047 题目链接 题意：一个由'E' 'O' 'F' 组成的长度为n的字符串。‘O’不能相邻。。问方案数。。 思路：递推。。。蒙对了（误 考虑第n位，如果为'E'或者‘F’，此时对n-1位没有限制，答案为f[n-1]，所以 一共是2×f[n-1] 如果为'O'，此时第n-1位为'E'或者'F'，此时对n-2位没有限制，答案为f[n-2],一共是2×f[n-2] 因此 f[i] = 2*(f[i-1]+f[i-2]) /* *********************************************** Author :111qqz Created Time :2016年07月27日 星期三 15时22分19 …

hdu2045 题目链接 题意： 一串 方格，每个格子可以涂三种颜色，要求相邻的格子颜色不能相同，首尾格子也不能相同。 思路：递推。没推出来23333 我好菜啊.jpg. 考虑有n个格子。。那么假设第n-1个格子的颜色是a,根据第一个格子和第n-1个格子颜色是否相同分为两种情况。 如果不相同，那么第n个格子不能和第1个格子颜色相同，也不能和第n-1个格子颜色相同，所以只有一种选择。 如果相同，那么第n个格子有两种选择。 /* *********************************************** Author :111qqz Created Time :2016年07月27日 星期三 14时53分16 …

hdu2018题目链接 题意:第1年有1头奶牛，每年生一头奶牛，新生的奶牛从生下来的第四年（包括生下来那年）也开始每年一头奶牛。 问第n年有多少头奶牛。 思路：最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1,而是dp[1..4]=1..4) 递推代码： /* *********************************************** Author :111qqz Created Time :2016年07月27日 星期三 13时19分17秒 File Name :code/hdu/2018.cpp …

hdu2084题目链接 题意：dp入门题。。。数字三角形。。 思路： 昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse... 为什么自底向上呢。。。 初始化dp[n][i] = a[n][i]其实是在处理只有最后一行的子问题。。。 需要特别强调的是。。处于某个子问题的时候。。。其他部分就好像不存在一样。。。 每一个点只能向下或者向右下两条路可走。。。 那么对于这一点的最大值。。。一定是取后来可走的两点的最大值加上自身。。。 /* *********************************************** Author :111qqz Created Time :2016年07月27日 …

hdu 4283题目链接 题意：有N个人按顺序排成一排上台表演，每个都有一个num[]值，若在他是第k个上场的人，则会有num[]*(k-1)的unhappiness。台下有一个黑屋（stack），对每一个人，可以选择让他先进屋子或者直接上台。现在让你找到一个最优方案使得所有人的unhappiness之和最小。 思路： 我想对了的： 无。状态设计就错了。。。转移方程也就不可能对。。。 错的一塌糊涂。。。嗯。。基础题。。完全不会2333 参考题解：参考博客1 参考博客2 /* *********************************************** Author :111qqz Created Time …

poj 3661题目链接 题意：锻炼，一共n分钟，每分钟可以选择跑步或者休息，第i分钟跑步可以跑d[i]米，并增加一点疲劳度，如果选择休息，那么每分钟减少1点疲劳值。一旦开始休息，必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0，否则之后会感觉身体被掏空。问n分钟最远多多远。 思路： 我能想到的： * dp[i][j]表示第i分钟疲劳度为j的时候能跑的最远距离 * 初始化dp为0. * 最后的答案为dp[n][0] * 如果第i分钟跑步，转移方程为dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]); 我想错了的： * 休息的时候的转移方程应该是第i天刚好** …

poj 1651题目链接 题意：n个数，删掉a[i]的得分是a[i]*a[i-1]*a[i+1]，两个端点的不允许删。问删完n-2个数得到的最小分数是多少。 思路：能想到设计状态dp[i][j]表示区间[i,j]的最小分数。然后就没思路了。 T T 参考了几篇题解，思路大概是，枚举最后剩下的那个数。 **对于一个区间(l, r),如果最后删除的是k位置的数的话，将得到a[l]*a[k]*a[r]分，而要得到这个情况的前提是吧区间(l, k) 和(k, r)的中间数字删掉所以的转移方程是** DP(l, r) = DP(l, k) + DP(k, r) + a[l]*a[k]*a[r]; 以及。。。初始化又想错了。。。 要注意。。初始 …

poj 3280 题目链接 题意：一个字符串，给出添加一个字符或者删掉该字符的花费，问最小的话费使得字符串变成回文串。 思路：dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。 这个可以想到。。dp[i][j] = dp[i+1][j-1] (a[i]==a[j])这个也可以想到。。。 增加和删除是等价的，所以取小的那个代价就行。。这个我也想到了。。 然后转移的地方没有特别明白。。。 和之前的找到一个划分的点k不同的是。。。 如果不等于。。 那么 , dp[i][j] = min(dp[i][j],dp[i+1][j]+cost[a[i]]); dp[i][j] = …

light oj 1422 题目链接 题意： 按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来，但是一旦脱下来，这件衣服就报废了。问最少需要几件衣服。 思路：没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这道题是道区间dp的入门题。。。但是不怕被鄙视。。我一点也没思路。。 参考了10多篇题解。。。终于懂了一点。。 参考博客1 参考博客2 参考博客3 参考博客4 **当a[i]和a[j]相等的时候 dp[i][j]=dp[i][j-1] 嗯，就这一个转移。然后就是区间dp的固定写法了。** 这句话让我恍然大悟。。。难道。。都是套路？ dp[i][j]表示的是[i,j]之间最少需要 …