题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。 思路：一开始很直接就想到把概率算成容量， 于是就成了经典的01背包，然后发现概率是double型。。。想当然得以为最多是2位小数，于是都*100转化成了整数做01背包。 然而正确思路是，把银行价值看成背包容量，而背包价值是概率！ 将危险的概率转化成安全概率（1-危险概率=安全概率) 然后做01背包。 然后从大到小扫一遍价值，第一个大于安全概率的就是答案。 注意精度。 /* …

题目链接 题意：给出n(n<=1E3)个字符，字符可能为'D','I','?'，第i位对应的字符分别表示，第i位大于第i+1位，第i位小于第i+1位，或者不确定。 现在问满足该字符串的 1..n的排列的方案数。结果9+7 思路：没有太多思路，参考了题解 主要是状态表示没有想到，后面的状态转移方程倒是不难。 思路是，dp[i][j]表示长度为i，最后一位的相对大小为j的方案数。 考虑转移：如果第i-1个位置的字符为‘I’，那么所有比j小的都可以转移到j，也就是dp[i][j] = dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j-2] + dp[i-1][j-1]; 如果第i-1个位置的字符 …

题目链接 题意：问长度为n的“波浪”型排列（即1..n每个数出现一次）有多少。波浪型的含义是，“高低高”或者“低高低” 思路：我们考虑当前已经知道i-1个数的波浪型的排列的方案数，那么当第i个数到来时，第i个数一定是最大的。 那么将i插入到某个位置，必须满足该位置前面必须以“高低”结尾，该位置后面必须以“低高”结尾才合法。（特别地，允许前面或者后面为空，这点体现在初始化上） 因此我们分别考虑，用dp[i][0]表示有i位且最后结尾为“高低”的方案数，dp[i][1]表示有i位且最后结尾为“低高”的方案数。 此时我们的情况是，已经有i-1个数，我要把第i个数插在某个位置。 这个位置是不确定的，因为我们需要枚举插入的位置（表现为，枚举插 …

1009: [HNOI2008]GT考试 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description 　阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。 他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为 0 Input 　第一行输入N,M,K.接下来一行输入M位的数。 …

题目链接 题意：问长度为n，每个位置由且仅有‘H’和'T'组成的序列中，至少有连续k个‘H’出现的方案数。 思路：不会做，参考了题解 不过没有完全搞懂。 根据题解，正面考虑比较麻烦，所以反面考虑。[j] dp[i][j]表示长度为i，前面最后连续的‘H’的个数不超过j个的方案数。 考虑转移方程为： 总的情况为：dp[i][j] = dp[i-1][j] * 2; 但是其中有多考虑的情况，就是第i位是'H'，且i位之前的最后j个位置都是'H'（即从i-j位到第i-1位都是‘H’，此时第i-j-1位必然是'T'） 有i个硬币时，如果i 如果i > j + 1，dp[ i ] [ j ] = dp [ i - 1 ] [ j ] * …

题目链接 题意：给出一个n个数的排列，每次可以把一个数放到最前面或者最后面的位置，问至少要进行多少次操作才能使得数列升序。 思路：考虑不被移动的那些数，当把所有一定的数去掉以后，这些剩下的数一定是一段数值连续，位置递增的数。如果想要移动的数最少，俺么这串递增的数就尽可能长。 dp[a[i]] = dp[a[i]-1] + 1 那么ans = n - max{dp[i]} 另外：对于要移动的数，我们可以按照一定顺序（放在前面的数按照递减顺序，放在最长序列后面的数按照递增顺序）移动，可以保证每个数只需要移动一次。 /* *********************************************** Author …

题目链接 题意： 给定两个序列，求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的 思路：以值为连续做入手点。 很显然个鬼咯 dp[a[i]]表示以a[i]结尾的最大长度。 dp[a[i]] = dp[a[i-1]] + 1 对于b序列一样。 答案为 MAX(min(dp[i],dp2[i])) ( 1=<i <= 1E6) /* *********************************************** Author :111qqz Created Time :Mon 26 Sep 2016 04:02:24 AM CST File Name :code/hdu/5904.cpp …

浅谈数形结合思想在信息学竞赛中的应用 参考博客 这个东西英文好像叫做：convex hull trick Convex_hull_trick_wiki codeforces convex hull trick 简单说说我的理解：斜率优化是一种数形结合的思想。。。 对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。 简单地说。。。如果把状态的下标和状态对应成二维平面的点。。。 凸起来的点一定不会影响答案。。。 具体证明参考论文。。。。。 也就是维护一个"下凸折线" 具体维护的办法是用单调队列来维护。。。 感觉还是挺简单的。。。。

hdu 5763 题目链接 题意：给定两个字符串A和B，每个出现在A中的B(可以overlap)都有两种含义，问A串一共可能有多少种含义。 思路：kmp+dp. 考虑dp[i]为前i个字符（也就是从开始长度为i，注意不是字符串的下标为i）的含义数。 我们考虑第i个字符对其他位置字符的贡献。 首先第i位的含义数可以无条件得转移到i+1位。也就是dp[i+1]+=dp[i]; 此外，如果第i位是一个B串开始的位置，那么第i位对i+len2位就有贡献。也就是dp[i+len2]+=dp[i]; 初始化dp[0]=1，其他为0. 剩下我们要做的就是处理出A串中的哪些位置是B串开始的位置。 kmp处理下就好，用一个布尔数组标记。 /* …

cf429 b 题目链接 题意： n*m个格子，每个格子有一个人value a[i][j]>0，连个人，一个从左上角到右下角，每次只能向下或者向右移动，一个从左下到右上，每次只能向上或者向右移动，现在要求两个人恰好相遇一次，相遇点的a不算数，问在满足这样的条件下使得两个人的a最大。。。（很坑的一点是。。这里相遇并不考虑时间。。就是说，不在同一时间都到达过某一格子，也认为相遇。所以我认为，题目含义更准确的说法是，路径只有一个交点） 思路：很巧妙。先预处理4个二维数组，分别表示点(i,j）到四个角落的最大值。（这个处理很容易，类似数字三角形） 然后枚举相遇的点，对于确定的相遇的点(x,y)，我们可以认为是四个角落各连一条线到 …