1
10
2013
0

USACO 4.3

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的单词单独打表,加上一些简单的剪枝,枚举两单词组合的情况不会超时。

 

Category: USACO | Tags: usaco | Read Count: 839

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com