首先,说以下本题目的状态转移方程为:
以d[ i ][ j ] = max ( d[ k ][ j +1 ] + sumc(i+1-->k , j+1) 其中sumc(i+1-->k , j+1)代表从i+1到k都到j+1避难 ) ;
首先说明为什么一定是连续 11...22..33...44..5..6 连续的取值;
所有 的 n支队伍和m个避难所要先排序;
我们可以假设最优解中除了必须的从n中取出的m个依次 对应 1 ,2, 3, 4,5,6,7直到m则这m只队伍一定是升序的,可贪心证明;
然后剩下的n-m支队伍会和在一起构成11...22..33...44..55..66..因为16...22..33...44..55..16. 任意两个位置错位则交换过来的解不......
阅读全文