先声明一下下述的变量

N为总天数,

A[i]表示第i个数字,

f[i]和g[i]的定义见下文

Max=max(f[i])1<=i<=N

第一问就是个最简单的最长下降序列,f[i]表示当前包含第i个数字的最长下降序列,

第二问稍复杂,我的分析:

1. 如果没有不能重复这个限制,非常好想到用g[i]存储当前包括第i个数字的最长下降序列的个数
   1. 如果f[i]被f[j]+1(j<i)更新,g[i]就更新为g[j]
   2. 如果f[i]等于f[j]+1,g[i]就更新为g[i]+g[j]
   3. 最后输出的方案数就是∑g[i] (f[i]=Max,1<=i<=N)
2. 如果加上不能重复这个限制,想一想会发现对于任意两个相同的数字A[i]和A[j](j<i),如果A[i-1]的值已经求出,那么之后的任何f[i]值都用不到A[j]了,因为f[i]>=f[j] 且 g[i]>=g[j],所以遇到A[i]=A[j]的情况就把A[j]标记为不可用,以后动态规划的时候就跳过j,这样就避免了重复,一下将证明该算法的正确性(分成两个独立的部分)
   1. 用数学归纳证明按照上述做法,当程序结束时g[i]表示的序列总数中没有任何重复:
      1. 首先对于i=1时,f[i]=1,g[i]=1只有一种方案,所以没有重复
      2. 对于N≥i>1,假设当前要求f[i]和g[i],那么对于1<=j<i的g[j]都是没有任何重复的(归纳假设)
      3. 只有A[j]>A[i]且f[i]=f[j]+1时才有可能发生重复,因为g[j]没有任何重复,所以g[i]有重复当且仅当枚举j的时候有A[j1]=A[j2]且j1≠j2(举个例子:3 2 1 3 2 1,要求f[6]和g[6],当j1,j2取1,4或2,5时显然重复了).
      4. 每遇到A[i]=A[j]就把A[j]删去,保证了数列元素唯一性
      5. 按照上述做法 可以做到没有j1,j2(j1≠j2)使得A[j1]=A[j2](因为数列保证了元素的唯一性) , 那么g[i]也是没有任何重复的.
      6. 注:其实上面的话可以简述为:因为算法保证了元素单调性,所以不可能发生重复
   2. 接下来证明g[i]没有少也没多计算任何情况(算出的g[i]是正确的)
      1. 容易看出g[i]不会比正确的结果大(删除序列元素不会增加答案)
      2. 假设某个被删除的元素为A[j],那么肯定有A[i]=A[j](i>j),而g[i]包括了g[j]的所有情况(g[i]≥g[j]),所以不会有任何一种非重复情况被遗漏
      3. 综上,算出的g[i]是正确的

我的代码(因为答案可能很大,所以用了高精度,并重载了"+"运算

4.1中的奶牛家秘术和Fence Rails都是要加好几个剪枝才可以AC的问题

搜索对象:每个栅栏(rail)对应那个Board(可能的深度太大而答案很可能在很浅的地方,所以迭代深度去找(DFSID),如果某个深度找到一个可行解,立刻退出,再搜索下一个深度)

一般优化都可以从以下3点考虑:

1.可行性剪枝   如果我们预料到某种情况无论再怎么搜索也得不到可行解,那就直接退出

2.最优化剪枝   如果我们预料到某种情况无论再怎么走索也得不到比当前最优解更优的解,那也直接退出

3.搜索顺序      良好的搜索顺序会更快的找到答案

其他技巧因问题而不同

那么Fence Rails可以这样剪枝:

1.可行性:     如果当前剩下的不可用的Board(即不能再切出rails的board)的和比board总面积减去rails的总面积还大,那肯定不可行(通俗地讲就是不能再装Rails的面积比装满所有rails剩下来的面积大)

2.搜索顺序:  容易想到,如果刚开始的时候就用大的rail塞到较小的board中,很快就能找到可行解

3.注意有很多重复,考虑到重复的元素位置不同没有影响,所以如果上一个元素和该元素相同,那么所在的board就直接从上一个开始枚举

这样就可以AC了

我的代码(有些慢):

1.构图

2.求出所有可能的满足拓扑序的答案并输出

1.的关键是题目的条件(每条边至少能看到1点)

2.这时用DFS求拓扑序好像就不管用了,所以采用暴力搜索去寻求答案,并满足拓扑序,

那就是记录一下每个矩形的出度,如果出度为0,说明当前可以继续搜(没有矩型被他压着),继续向下搜索,并删除该矩形(把压着他的矩形的出度-1),然后递归到下一层再找出度为0的矩形,这样就可以了.

描述

看下面的五张 9 x 8 的图像：

........   ........   ........   ........   .CCC....
EEEEEE..   ........   ........   ..BBBB..   .C.C....
E....E..   DDDDDD..   ........   ..B..B..   .C.C....
E....E..   D....D..   ........   ..B..B..   .CCC....
E....E..   D....D..   ....AAAA   ..B..B..   ........
E....E..   D....D..   ....A..A   ..BBBB..   ........
E....E..   DDDDDD..   ....A..A   ........   ........
E....E..   ........   ....AAAA   ........   ........
EEEEEE..   ........   ........   ........   ........

   1          2           3          4          5 

现在，把这些图像按照 1—5 的编号从下到上重叠，第 1 张在最下面，第 5 张在最顶端。如果一张图像覆盖了另外一张图像，那么底下的图像的一部分就变得不可见了。我们得到下面的图像：

 .CCC....
 ECBCBB..
 DCBCDB..
 DCCC.B..
 D.B.ABAA
 D.BBBB.A
 DDDDAD.A
 E...AAAA
 EEEEEE.. 

对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。

下面是这道题目的规则：

• 矩形的边的宽度为 1 ，每条边的长度都不小于 3 。
• 矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。
• 矩形用大写字母表示，并且每个矩形的表示符号都不相同。

PROGRAM NAME: frameup

INPUT FORMAT(file frameup.in)

OUTPUT FORMAT

SAMPLE OUTPUT (file frameup.out)

按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。

SAMPLE INPUT (file frameup.in)

9 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE.. 

SAMPLE OUTPUT (file frameup.out)

EDABC