[题解]区间dp_luogu_P3147 262144

小数据版本P3146,可以区间dp,

性质:对于一个区间如果能合并成一个数,那么这个数是确定的

理解:把每个数看做 2^x 的形式,那么如果合并:2^x + 2^x =2^(x+1)

所以 f [ i ] [ j ] 表示 i 到 j 能合并成的数x,不能合并成一个数则为-1

               { x (f [ i ] [ k ]==f [ k+1 ] [ j ])

f [ i ] [ j ]={

               { -1

对于大数据发现n为2的18次方,而开始的数只有1-40,所以发现最大只能拼到58,另一种dp方法

f [ i ] [ j ]表示从下标 f [ i ] [ j ] 到 i 会拼成 j ,即到 i 为止能拼成 j 的左端点

           { f [ i-1 ] [ f [ i-1 ] [ j ] ];( f [ i ] [ j ]==0 )

合并的话就是 f [ i ] [ j ]={

           { j ( f [ i ] [ j ]==1 )

原文地址:https://www.cnblogs.com/superminivan/p/10661443.html