Problem1077--[视频]动态规划入门(非常规DP1:筷子)

1077: [视频]动态规划入门(非常规DP1:筷子)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Status] [Submit] [Creator:]

Description

【问题描述】
        共N根筷子,长度为T1,T2,T3,……,TN。组成K+3对,使每双的筷子长度差的平方和最小。
【输入文件】
        输入文件共有两行,第一行为两个用空格隔开的整数,表示N,K(1≤N≤100,0<K<50),第二行共有N个用空格隔开的整数,为Ti每个整数为1~50之间的数。
【输出文件】
        输出文件仅一行。如果凑不齐K+3双,输出-1,否则输出长度差平方和的最小值。
【样例输入】
10 1
1 1 2 3 3 3 4 6 10 20
【样例输出】
5
【数据说明】
第一双 1 1
第二双 2 3
第三双 3 3
第四双 4 6
(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5
有证明的成分,应该说证明的成分比较多,搞定证明就能减少状态的搜索,状态方程就好解决了。!
这题含有贪心的策略,然后才能动态规划。  算是 质量比较好 的题。  

HINT

 

Source/Category