简单动归，蛋疼的是开longint会爆- -！ 囧~
dp[i,j]表示前i个有j个上升序列的个数，方程dp[i,j]:=dp[i-1,j-1]*(i-j+1)+dp[a-1,b]*b ，意思是要转移成当前状态需要两种状态转移过来，分别对应加上当前数后序列个数增加和不增加两种情况，边界值dp[i,1]:=1,i∈[1,n].

@Makazeu 自己动手，丰衣足食

如果暴力枚举的话，算出n=20的情况需要15000年

没有插件的话，，这题怎么写？

s在扯淡无误，话说变量名打错居然还能40分，rp总在无意中流失啊~，钱的总量和物品价值还是刚开始就除以10好了，

2L 大神装弱菜。rp会掉，怒捡！

由于前一天比赛的原因，我还是写了高精度。。。应该先验证一下要不要写的。。。

背包问题是没问题，不过还是处理的复杂了，m 只有 60 还是很小的嘛。s 根本是在扯淡。

BFS状态最多2^15-1种，秒之

从10X10的表找规律，
然后每个程序现场打表（好浪费……），再输出

比赛时先写了个单向的bfs，后面又写了个双向的，结果双向的wa了一个点而单向的却AC了

上午的打开O2优化过了
下午的不开O2优化过了
方法是一样的：泛化背包
优化处理：
1、数组降维。减少不必要的循环次数。
2、并不是把所有的背包都当做泛化背包，生成泛化函数，而是仅把有附件的背包泛化处理。

先用 STL 枚举出来一个表（算到 n=12 就出不来了）

1: 1
2: 1 1
3: 1 4 1
4: 1 11 11 1
5: 1 26 66 26 1
6: 1 57 302 302 57 1
7: 1 120 1191 2416 1191 120 1
8: 1 247 4293 15619 15619 4293 247 1
9: 1 502 14608 88234 156190 88234 14608 502 1
10: 1 1013 47840 455192 1310354 1310354 455192 47840 1013 1
11: 1 2036 152637 2203488 9738114 15724248 9738114 2203488 152637 2036 1
12: 1 4083 478271 10187685 66318474 162512286 162512286 66318474 10187685 478271 4083 1

然后找规律 \[ f_{i, j} = (i - j + 1) \times f_{i-1, j-1} + j \times f_{i-1, j} \] 要用 long long ，高精度暂时不必～

先暴力next_permutation，然后递推。

BFS。又在用 STL 了……

DP+单调队列优化。。。GJ。。。【我可怜的边界。。。我可怜的队列。。。。我比⑨都⑨诶………………

http://wenku.baidu.com/view/aa9dd907bed5b9f3f90f1c8b.html

これはPVを見たら涙腺破壊される！！！！！！

我先是看了Chrome写的是否翻译，然后点了否。
然后看题，然后逐字地看题。
然后看了输入输出格式。
然后有部分没看懂，然后回去又看了一遍。
然后又有一些部分没看懂，然后回去又看了一遍。
然后我往下接着看了两行。
然后就没有然后了。
@ ⑨

仰慕二位大犇。。@Makazeu @PaulInsider