第一题：只要按照题意，对每只兔子，检测两边的距离就好了，复杂度O(n)
第二题：想了很久没做出来，后来看了别人的代码后才想到，刚开始兔子的位置是无所谓的，只需要按照preferences从小到大排序，然后从小到大用排列公式即可，例如2 3 4，则第一只可以选择1，2两种可能，第二只可以选择3-1中可能，第三只可以选择4-2种可能。。。相乘即可~
第三题：第一眼看去和石子问题很像，不过这个可以是任意两个，太久时间没看dp了，基本都忘得差不多了。。。。，这道题的dp应该是属于区间模型。由于题目中的数据很特殊（1.5~10),对于任意一个大于3的数a和任意一个大于1.5的数b,有a*b>a+b,且任意两个大于1.5的数的和大于3，故每个数最多只有被加一次的机会。现在设f(i,j)表示从i到j区间上的最大值，则状态转移公式可以表示为：
f(i,j)=max{num[i]*f(i+1,j),f(i,j-1)*num[j],(num[i]+num[j])*f(i+1,j-1)}.
需要注意的是自顶向下实现的时候，如果i>j则返回1而不是返回0.
阅读(432) | 评论(0) | 转发(0) |
