题目一:energy
题目的意思是在这个环内选两个数合并成新的数,接着再继续合并,找到其合并的最大值,有可以理解为找一点断开,然后再进行合并,求其最大值,其算法为枚举+最小子母代价树(DP);其方程为:
F[I,J]=MAX{F[I,K]+F[K+1,J]+A[I]*A[K+1]*A[J+1]}(1<=I<=N,I<=J<=I+N,I<=K<=J)
F[I,I]:=0;
注意:1、求解时是将环线性化,所以要开到3*N的数组;
2、枚举是枚举断开数字的位置;
题目二:budget
题目的方法是背包问题。但是要进行预处理,把所有的附件都组合在一起(因为附件最多只有两个,且附件没有在属于它的附件,所以最多只有四钟情况,主件,主件+附件1,主件+附件2,主件+附件1+附件2,即分解成几种物品)方程为:
F[I,J]:=MAX{F[K,J-PV[I]]+PW[I];F[K,J]}(1<=I<=MM,0<=J<=N,0<=K<=I-Q[I])
F[0,0]:=0;
注意:1、Q[I]是前一个主件到这个主件的相对距离(有附件的存在);
2、PW[I]是第I个物品的价值,PV[I]是第I个物品的重量(要在前面求出来);
3、MM是预处理之后的总件数;
4、最后的答案要扫描一遍输出的,或是边动归边记录最大值;
题目三:jsp
题目算法简单:模拟法,扫描每个任务和该任务要在哪个机器上完工,然后再把这任务在该机器上的时间插入其时间空当(可用布尔数组代表这一时刻有没有机器在这里工作),最后输出这些机器完成所有任务的最后时间(最大值);建议多读几遍题,把重要内容标记好,会有好的收获的;
题目四:digital
数学题目,理解为从第二段开始使前面的数小于后一位的数,递推式为:
F[I,J]:=F[I-1,J+1]+F[I,J+1];
ANS:=ANS+F[I,J];
(2<=I<=(K-1) DIV R;1<=J<=2^R-1)
最后I=(K-1)DIV R+1时,1<=J<=2^(K-((K-1)DIV R)*R)-1
其式子可以从题目和样例推出来,至于精度方面:LONGINT 过五组数据INT64过七组数据 处理高精度全过(可以用LONGINT测试程序是否正确)
注意:数组可以开两个一维的高精数组,当前状况只与上一层状况有关,所以这样可以节省空间。