首页 > 代码库 > 习题:就是干(DP)
习题:就是干(DP)
洛谷2301
题目描述
眼看着老师大军浩浩荡荡的向机房前进。LOI 的同学们决定动用自己的力量来保卫他们的好朋友loidc。现在每个人都要挑选自己的武器——两根木棍。一根用做远距离投掷,另一根用做近距离搏斗。每个人都想挑到最好的,但这是不可能的。但是为了让多数人满意,也为了减少大家的矛盾。cony设计了一个矛盾指数,这个指数就是每个人的不舒服指数和,不舒服指数就(L1-L2)^2,其中L1,L2分别是两根木棍的长度。
cony决定让矛盾指数最少,于是他来向你寻求帮助,希望你能告诉他矛盾指数至少有多少。
输入输出格式
输入格式:
第一行两个数m,n.
表示有n个人,m个木棍。
接下来m个数表示每个木棍(肯定有解)。
(m<=2000,n<=500)
输出格式:
一个数,最少的矛盾指数。
输入输出样例
输入样例#1:
5 2
3
1
4
5
8
输出样例#1:
5
分析:
先排序,显然组成一对的木棍必相邻才是最优的。
故得到方程
f[i,j]=min(f[i-1,j],f[i-2,j-1]+sqr(a[i]-a[i-1])) i=2..m
初值f[i,0]:=0;
代码:
program work; var f:array[0..2000,0..500]of int64; a:array[0..2000]of int64; n,i,m,j:longint; t:int64; function min(x,y:int64):int64; begin if x<y then min:=x else min:=y; end; begin readln(m,n); for i:=1 to m do readln(a[i]); for i:=1 to m-1 do for j:=i+1 to m do if a[i]>a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; for i:=0 to m do for j:=1 to n do f[i,j]:=maxlongint*100; f[1,0]:=0; f[0,0]:=0; for i:=2 to m do for j:=1 to min(m div 2,n) do f[i,j]:=min(f[i-1,j],f[i-2,j-1]+sqr(a[i]-a[i-1])); writeln(f[m,n]); end.
习题:就是干(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。