DP题,只有分想到与想不到....
这里定义f[i]用来存储有i种pearl时的最小花费,则这里可以得出以种类数为状态的动规,先给出转移方程
f[i]=min{f[j]+(need[k]+need[k+1]+...+need[i]+10)*price[i]}(1<=k<=i),(0<=j<i)(初始化 f[0]=0)
这里由方程可以看出,是将种类j和i之间的pearl都按照i的价格计算得出的最小值,j的取值为小于i的任意非负整数,当j=0是,即将所有pearl都按照第i中的价格出售的总值,由于不存在第0种的情况,故数量求和时,k从1开始。
DP题还是多做才能掌握啊...
代码: