首页 > 代码库 > USACO泛做
USACO泛做
打扫卫生
题意：一段序列，分为若干段，每段分值为该段中不同数字个数平方，求划分方案使分值和最小。
分析：n^2DP很好写 f[i]:=min(f[j]+cost[i+1,j]); 考虑优化，由于任何序列其最小分值和最大为n（每个元素自成一段），故可推出最优方案中，每段分值不可能超过n，也就是不同元素个数不超过根号n，故方程改为f[i]:=min(f[b[j]]+j*j); j<=√n; b[j]表示一个位置编号，意思是从i开始到b[j]+1，共有j个不同的数字，然后维护即可。
program cleanup;var f,a,b,c,hash:array[0..100000]of int64; n,m,t:int64; i,j:longint;function min(x,y:longint):longint;begin if x<y then min:=x else min:=y;end;begin readln(n,m); for i:=0 to m do hash[i]:=0; for i:=1 to n do read(a[i]); m:=trunc(sqrt(n)); f[0]:=0; for i:=1 to n do begin f[i]:=maxlongint; for j:=1 to m do if hash[a[i]]<=b[j] then inc(c[j]); hash[a[i]]:=i; for j:=1 to m do if c[j]>j then begin t:=b[j]+1; while hash[a[t]]>t do inc(t); b[j]:=t; dec(c[j]); end; for j:=1 to m do f[i]:=min(f[i],f[b[j]]+j*j); end; writeln(f[n]);end.
USACO泛做
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。