Vijos 1306 递增序列 解题报告

用f[i]表示以i结尾的最长序列长度，可以证明在序列长度相等的情况下，最后一个数的长度越小则第一个数的长度越大（即倒序枚举j）。用g[i]记录当f[i]取得最大值时以第i位结尾的数字字串。由此可得状态转移方程：f[i]=max(f[i],f[j]+1)(1<=i<=length(s),1<=j<=i,g[i]>g[j])。递归求解（用g[length(s)]的长度可以推出前一个状态）输出答案即可。

R1124895 Accepted 100 From IwfWcf－ P1306 FPC Vijos Dolphin 2009-1-28 21:06:20