TYVJ1191（迎春舞会之三人组舞）

算法：DP
看起来短短的不到50行的代码，但是从构建DP方程来说，本题确实属于难题。
DP方程：f[i,j]:=min(f[i,j],min(f[i-1,j],f[i-2,j-1]+sqr(a[i-1]-a[i])));

思路是只分站在两边的人，而站在中间的人不参加计算，同时要选最小的一定是选邻近的，因为邻近的差值最小。

program P1191;constmaxn=5000;maxm=1000;vara:array [0..maxn] of longint;f:array [0..maxn,0..maxm] of longint;{f[i,j]表示前i个人分成j组的最小残废程度。目标就是f[n,m]。}m,n:longint;procedure init;
vari:longint;
beginreadln(m,n);for i:=n downto 1 do read(a[i]);{倒着记录，即a[1]最大，a[n]最小。}fillchar(f,sizeof(f),100);{求最小，初始化成最大。}for i:=1 to n do f[i,0]:=0;{前i个数分成0组的最小残废程度肯定是0。}f[3,1]:=sqr(a[3]-a[2]);{这个手工计算一下，前3个数分成1组。}
end;function min(x,y:longint):longint;
beginif x>y then exit(y) else exit(x);
end;procedure main;
vari,j:longint;
beginfor i:=4 to n do{3的算过了，从4开始算。}beginfor j:=1 to m do

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！