题目大意是一个线段分成n段涂色，有m种颜色可用，给出每种颜色的费用，每一段规定了所用的颜色以及涂色长度区间。同种颜色的涂色长度不能相同，求是否能按要求完成涂色以及最少需要花费的费用。
很典型的搜索题，主要用到了2个减枝技巧：
其中第二个预处理通过O(nl^2)的DP完成。
2353428 2010-11-19 02:08:21 Accepted 2633 C++ 1320 212 IwfWcf
题目大意是一个序列a[i]要求满足a[i]>0，a[i]>=2*a[i-1]且a[n]<=k，现给出n和k，求所有满足条件的序列的数量。
用f[i,j]表示第i个数以j结尾的序列数量，则f[i,j]=∑f[i-1,k](2^(i-2)<=k<=j/2)，边界条件是f[1,i]=1。ans=∑f[n,j](2^(n-1)<=j<=k);
1653745 2008-10-02 12:41:29 Accepted 2402 FPC 50 424 IwfWcf
题目大意是求n的全排列中逆序对数为k的排列数。
n的全排列可以看作是将n插入n-1的全排列中生成的，而对于n-1的全排列来说，n有n个插入位置，将n插入第i个位置可以增加(n-i)对逆序对。所以可以得到递推式f[i,j]=∑f[i-1,j-k](0<=k<=i-1)，边界条件是f[1,0]=1。
1653710 2008-10-02 11:39:31 Accepted 2284 FPC 0 144 IwfWcf
题目大意是26个字母对应的编号分别是1-26，给出一串编码，问有多少种解码。
用f[i]表示编码的前i个字符的解码数量，f[i]=f[i-1]+f[i-2](s[i-1..i]<=26,s[i-1]<>0,s[i]<>0);f[i]=f[i-1](s[i-1..i]>26 or s[i-1]=0);f[i]=f[i-2](s[i]=0);其中s[i]表示编码的第i个字符。由于f[i]只与f[i-1]和f[i-2]有个，所以可以用滚动数组优化空间。
1653645 2008-10-02 10:43:15 Accepted 2202 FPC 0 112 IwfWcf
题目大意是两个字符串进行匹配，给定每个字符匹配的得分，每次匹配完成后该字符前的字符串将被删除，求最高匹配得分。
带权LCS（最长公共子串）模型。用f[i,j]表示第一个字符串前i个字符与第二个字符串前j个字符匹配的最高得分，则f[i,j]=max(f[i-1,j-1]+v[s1[i]],max(f[i-1,j],f[i,j-1]))(s1[i]=s2[j]);f[i,j]=max(f[i-1,j],f[i,j-1])(s1[i]<>s2[j]);s1[i]表示第一个字符串的第i个字符，s2[j]表示第二个字符串第j个字符，v[s1[i]]表示s1[i]的匹配得分。
1653610 2008-10-02 10:01:55 Accepted 1642 FPC 70 16040 IwfWcf
题目大意是给出一个矩阵，求出矩阵中某些指定子矩阵的所有元素的平方和。
先利用递推预处理出所有以(1,1)为左上角的矩阵的所有元素的平方和。用f[i,j]表示左上角为(1,1)，右下角为(i,j)的矩阵的所有元素的平方和，则f[i,j]=f[i-1,j]+sum[j];sum[j]表示第i行前j个元素的平方和。则所求子矩阵(r1,c1,r2,c2)的所有元素平方和即为f[r2,c2]-f[r1-1,c2]-f[r2,c1-1]+f[r1-1,c1-1]。
1653473 2008-10-01 23:50:40 Accepted 1636 FPC 140 1092 IwfWcf
题目大意是求一段序列中子序列之和除m余0的子序列数量。
用sum[i]表示∑a[i]，题目所求即所有(sum[i]-sum[j]) mod m=0的组合数量（包括sum[0]）。(sum[i]-sum[j]) mod m=0即sum[i]与sum[j]除m的余数相同，所以可以记录sum[i]除m的每种余数的数量。用f[j]表示sum[i]除m余j的数量，则ans=∑f[j]*(f[j]-1)/2。
1653449 2008-10-01 23:23:58 Accepted 1569 FPC 10 120 IwfWcf
题目大意是在1991.1.1-2001.11.4中抽取一个日期，可以对其进行两种操作，月+1或日+1，将其变为2001.11.4时游戏即结束，问先手有无必胜策略。
除了9.30和11.30外，其它日期对其进行任何一个操作都会改变其（月+日）的奇偶性。由于目标状态的（月+日）为奇，所以除上述两个状态外（月+日）为偶的都是先手必胜态。9.30和11.30都可以转化为必败态（10.1和12.1），所以其自身即为必胜态。
1653402 2008-10-01 22:35:27 Accepted 1024 FPC 0 112 IwfWcf
题目大意是给出一个括号序列中每个右括号左边的左括号的数量，要求输出与每个右括号匹配的是其左边的第几个左括号。
用一个布尔数组模拟括号匹配过程即可。
题目大意是求用给定的m个组合组成长度为l的字符串的方案数。
先进行预处理，标记可以作为某些组合的前缀的某些组合的后缀。用f[i,j]表示第i个位置为第j种组合的方案数，则f[i,j]=∑f[i-1,k](pre[j]=last[k]);pre[j]表示第j种组合的前缀，last[k]表示第k种组合的后缀。则所求方案数为∑f[l,j]。
1652446 2008-09-30 22:40:08 Accepted 1800 FPC 660 716 IwfWcf@LZOI
题目大意是给出两个字符串进行匹配，如果两个字符串的长度不等则用空格将其补齐，如果两个字符串匹配的对应位置字符相等则得2分，不等（不包括空格匹配）扣两分。如果用空格进行匹配则连续的k个空格（在同一个字符串中）的得分为-(4+k)。问两个字符串匹配的最高得分是多少。
依然是LCS（最长公共子串）的模型，由于要考虑空格匹配得分的影响，可以将每次匹配分为三种情况考虑：
由此可以得到的状态转移方程：
s1[i]表示的是第一个字符串的第i个字符，s2[j]表示的是第二个字符串的第j个字符。f[i,j,0]表示的是用s1的前i个字符与s2的前j个字符匹配，且当前用s1[i]与s2[j]进行匹配的最高得分，f[i,j,1]表示的是用s1的前i个字符与s2的前j个字符匹配，且当前用空格与s2[j]进行匹配的最高得分，f[i,j,2]表示的是用s1的前i个字符与s2的前j个字符匹配，且当前用s1[i]与空格进行匹配的最高得分。初始化f[i,0]=-(4+i),f[0,i]=-(4+i);
1652376 2008-09-30 21:05:35 Accepted 1792 FPC 10 3340 IwfWcf
题目大意是有n种等级的珍珠，如果要买某种珍珠就必须比预定购买数量多买10粒，低等级的珍珠可以用高等级的代替，给出要买的每种等级的珍珠的数量和单价，求要买够所有珍珠需要花费的最少价格。
用f[i]表示买前i种等级的珍珠需要花费的最少价格，则f[i]=min(f[i],f[j]+(sum[i]-sum[j]+10)*p[i])(0<=j<i);sum[i]为前i种等级的珍珠的预定购买量之和。
1651905 2008-09-30 00:04:51 Accepted 1563 FPC 0 112 IwfWcf
题目大意是一个人有g次猜数机会和l条生命线，每次猜数如果猜错了则扣除一次猜数机会，如果猜高了还要扣除一条生命线，如果在没有生命线的情况下猜高了就输了。问在有g次猜数机会和l条生命线的情况下最多能保证正确猜出多少以内的数？
用f[i,j]表示g=i,l=j的情况下可以保证猜中的最大数，将每次猜数分成三种情况，猜低、猜中和猜高，则可推出状态转移方程f[i,j]=f[i-1,j]+1+f[i-1,j-1];由于l=0的情况下只能猜低的数，因此初始化f[i,0]=i;
1651819 2008-09-29 22:39:48 Accepted 1503 FPC 0 116 IwfWcf
题目大意是求出用1、2、3、5、7这5个数字配合+、*、^、!这四种运算符得出表示n(n<=20000)的最简表达式（即所用数字最少）。
显然+和*两种情况的处理都比较简单，比较麻烦的是^和!的运算。不过20000内的!运算情况只有7种，因此可以对!运算进行特别处理。而对于^运算，若x^i=n，则可以用g[n,i]来记录x，通过预处理即可得到20000内所有^运算的方案。同时为了方便起见，最好将4和6的情况也预处理一下。完成了以上预处理后即可，用f[i]表示组成i所需的最少数字，则有几种情况需要处理：
同时在DP过程中记录下转移到当前状态的前一个状态，这样即可利用递归输出所求表达式。
1651204 2008-09-28 23:42:58 Accepted 1446 FPC 280 444 IwfWcf
题目大意是给出n，判断n的因数和与n的大小关系。
似乎有一条数学公式可以求出n的因数和，不过由于不知道那条公式且数据很小，所以直接用模拟来做。
1650684 2008-09-27 22:44:51 Accepted 1284 FPC 0 112 IwfWcf
题目大意是给出一个点序列和一些单词，每个字母可以转换成对应的点序列，求题目所给出的点序列用所给单词组成的方案数。
预处理时先将单词全部转换成点序列，用f[i]表示到点序列的第i位能够用所给单词组成的方案数，则f[i]=∑f[j](s[j+1..1]为所给单词转换成的点序列)。
1650680 2008-09-27 22:37:41 Accepted 1387 FPC 9300 1296 IwfWcf
题目大意是给出一张由若干小三角形构成的三角形纸，其中有的小三角形破损了。问现在能够从纸上剪下的最大的三角形面积有多大。
假如我们用f[i,j]表示第i行第j个倒向的三角形能构成的三角形的最大高度，则显然f[i,j]=min(f[i-1,j-1],f[i-1,j+1])+1(map[i-1,j]='-');类似的，用g[i,j]表示第i行第j个正向的三角形能构成的三角形的最大高度，则g[i,j]=min(g[i+1,j-1],g[i+1,j+1])+1(map[i+1,j]='-');max(f[i,j],g[i,j])^2即为所求。
1650678 2008-09-27 22:36:05 Accepted 1245 FPC 0 172 IwfWcf
题目大意是给出位于一直线上的n家餐厅与原点的距离，要求在其中选k家作为供应站，输出供应所有餐厅的最短路程。
如果用f[i,j]表示在前j家餐厅设立i个供应站时，供应j家餐厅的最短路程，则很容易想到f[i,j]=min(f[i-1,k]+g[k+1,j])(k<j);g[k+1,j]表示在第k+1到第j家餐厅设立一个供应站，供应这些餐厅的最短路程。显然这一供应站应该设立在中点，因此进行这一预处理后就可以进行DP了。
1649566 2008-09-23 17:00:00 Accepted 1196 FPC 10 584 IwfWcf
题目大意是给出两个字符串，输出包含这两个字符串的最短字符串。
本题模型同样是字符串DP中非常常用的LCS（最长公共字串）模型，用f[i,j]来表示包含第一个字符串前i位和第二个字符串前j位的最短字符串，则可以分两种两种情况考虑，若s1[i]=s2[j]，则f[i,j]=min(f[i-1,j-1],min(f[i-1,j],f[i,j-1]))+s1[i];否则f[i,j]=min(f[i-1,j]+s1[i],f[i,j-1]+s2[j])。
1649561 2008-09-23 16:57:25 Accepted 1953 FPC 0 596 IwfWcf
题目大意是给出一段括号序列，要求添加最少括号使其成为规则序列并输出。
本题属于在区间内进行DP的题目，用f[i,j]表示从序列的第i-j段需要添加的最少括号数。可以分成两种情况考虑，一种是i和j恰好能够匹配，另一种是i和j无法匹配。如果是前者则f[i,j]=min(f[i+1,j-1],f[i,k]+f[k+1,j]);否则f[i,j]=min(f[i,k]+f[k+1,j]);并且在DP过程中记录下转移到当前状态的前一个状态，利用此递归输出答案即可。
1649555 2008-09-23 16:54:23 Accepted 1463 FPC 0 420 IwfWcf
博文
所有评论
