问一道编程题目,有pascal代码,但看不懂,谁能帮我解释一下?

2025-02-26 02:23:08
推荐回答(2个)
回答1:

这个题目比较简单,是一个DP+优化
我们用f[i]表示将前i头牛划分成若干组的方案总数,用s[i]表示前i头牛的乐观值之和,那么就有
f[i]:=sum(f[k])其中1<=k=0,sum表示求和,这个转移方程很好理解,但是,时间复杂度为O(n^2),对于题目给定的数据范围无法承受,于是,需要优化,我们想到了树状数组
要转移,必须得两个条件是1<=k=0,对于前者,我们按照i从小到大的顺序进行处理,就可以满足:对于所有s[i]-s[j]>=0,sum(f[j])=sum(f[k]),因为当处理i时,若x大于i,f[x]函数值还没有处理,为空.
关键在满足s[i]-s[k]>=0这个条件上,我们先对s进行排序,问题转化为对于给定的i,求出s[k]<=s[i]的f[k]的总合..应用树状数组,将排序后的s的顺序离散为数组的下标,之后每次求f[i],只需要求对应下标比s[i]小的,树状数组内的区间和,之后对应着s[i]的位置将计算完的f[i]插入树状数组,注意一下s[i]相同时的处理.
树状数组的区间和维护需要的时间复杂度是O(logN)的,所以整个程序的时间复杂度是O(NlogN),可以满足题目的数据范围需求............算法解释完毕

procedure ini(key,nu:longint);是树状数组的插入
function find(key:longint):longint;是树状数组的区间求和
function get(key:longint):longint;二分查找s[i]在树状数组中对应的位置
procedure prep;读入数据,预处理s[i]
sort排序不解释

整题圆满解决! 请采纳....

回答2:

如果要我解释pascal,我可以解释。但要我解释算法的话,就力有未逮了,因为我连题目都看不太懂。