• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1260 – Pearls

    ACM-POJ EXP 147阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给出几类珍珠,以及它们的单价,要求用最少的钱就可以买到相同数量的,相同(或更高)质量的珍珠。

    【规定买任一类的珍珠n个(价格为p),都要支付(n+10)*p的钱,即额外支付10*p】

    解题思路

    例如样例Input的第二个例子:

    3

    1 10

    1 11

    100 12

    需要买第一类1个,第二类1个,第三类100个

    按常规支付为 (1+10)*10 + (1+10)*11 + (100+10)*12 = 1551元(一共买了102个珍珠)

    但是如果全部都按照第三类珍珠的价格支付,同样是买102个,而且其中总体质量还被提高了,但是价格却下降了:(102+10)*12 = 1344元

    而对于样例Input的第一个例子:

    2

    100 1

    100 2

    按常规支付为 (100+10)*1 + (100+10)*2 =330元

    但是全部按第二类珍珠的价格支付,同样买200个,虽然总体质量提升了,但是价格也提高了: (202+10)*2=424元


    本题关键点在于:

    (1) 要求要买的珍珠的数量是一定的

    (2) 所买的珍珠的质量允许提高,但不允许下降(即可以用高质量珍珠替代低质量)

    (3) 输入时,后输入的珍珠价格一定比前面输入的要贵

    (4) 由(2)(3)知,珍珠的替代必须是连续的,不能跳跃替代(这个不难证明,因为假如用第i+2类去替代第i类珍珠,会使最终的支付价格降低,那么用第i+1类去替代第i类珍珠会使最终的支付价格更加低)

    根据这4个约束条件,那么购买珍珠的方案为

    在珍珠类型的总区间[1,c]中划分多个子区间,其中在闭区间i1~j1的珍珠全部按第j1类珍珠的价格p1支付,在闭区间i2~j2的珍珠全部按第j2类珍珠的价格p2支付,…在闭区间in~jn的珍珠全部按第jn类珍珠的价格pn支付。 这些区间互不相交。

    其余珍珠按其原价支付。

    要求找出最优的划分方案,使得最终支付价格最低。

    令dp[i]表示在已知第i类珍珠时,所需支付的最低价格

    状态方程为:

    dp[i]=(a[i]+10)*p[i]+dp[i-1]; //当第i种珍珠出现时,未优化价格的情况

    dp[i]=min(dp[i],(sum[i]-sum[j]+10)*p[i]+dp[j]); //枚举j,价格优化

    dp[0]=0; //Dp初始化

    转载请注明:EXP 技术分享博客 » POJ1260 – Pearls

    喜欢 (1) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址