1.Buy Low, Buy Lower
动态规划
求最长下降子序列的长度和个数。
设序列为a[0]...a[n]
用dp[i]表示以a[i]为结尾的最长下降子序列的长度，则
dp[i]=max{dp[j]+1}(j<i and a[j]>a[i])
用total[i]表示以a[i]结尾的互不相同的最长下降子序列的个数，则
total[i]=∑total[j] (j<i and a[j]>a[j] and dp[j]+1==dp[i])
注意去重，如果有多个符合条件的j对应相同的a[j]我们只加入最大的j对应的total[j]，
这是因为如果u>v且a[u]==a[v]，以a[v]为结尾的所有序列都包含于以a[u]为结尾的序列集合。
2. The Primes
搜索+剪枝
对五位且数位和一定的素数打表。
先放对角线上的两个素数，注意左上角数字是确定的，左下角是一个素数的结尾所以必须为奇数。
然后顺序枚举第1、2、3行上的素数，之后第4、5行可以算出来，记录可行解。
排序输出。
由于每列都是素数，可以打表记录下一些素数“特征”是否存在，用于剪枝，比如有素数为11351，就记 head[1]=head[11]=head[113]=head[1135]=true，如果枚举过程中出现了一些“特征”不存在（对应的head值为 false）就剪枝。另外一定要充分利用已经放置的数的信息进行提前剪枝，比如枚举到第三行素数，可以得到第二列和第四列的前四位数，即可比对这些“特 征”是否存在。
3.Street Race
枚举去掉的路口，如果去掉后从起点floodfill不能到达终点，则此路口unavoidable。
如果从一个unavoidable的路口出发不能回到起点可达的路口，则此路口是splitting point。
4.Letter Game
首先注意到由于目标词长度最大为7，那么最多只有两个字母组合，且只有长度为3或4的单词可以组合在一起。
对长度3或4的单词单独打表，加上一些简单的剪枝，枚举两单词组合的情况不会超时。
评论 (0)
