时间戳

首页 > 解决方案 > 对于 spoj 的问题 TRT（对待奶牛），最好的 dp 方法是什么？

c++ - 对于 spoj 的问题 TRT（对待奶牛），最好的 dp 方法是什么？

问题描述

FJ 购买了 N (1 <= N <= 2000) 种美味的零食给那些因提供大量牛奶而赚钱的奶牛。FJ 每天销售一份零食，并希望在给定的时间段内最大化他收到的钱。这些款待很有趣，原因有很多：

零食编号为 1..N，并按顺序存储在一个长盒子中的单个文件中，该长盒子两端都打开。在任何一天，FJ 都可以从他存放的零食的任一端取回一份零食。就像精美的葡萄酒和美味的奶酪一样，这些零食会随着年龄的增长而提高，价格也会更高。款待并不统一：有些更好，具有更高的内在价值。对待 i 的值为 v(i) (1 <= v(i) <= 1000)。奶牛为年龄较长的零食支付更多费用：一头奶牛将为年龄为 a 的零食支付 v(i)*a。给定按照盒子中索引 i 的顺序排列的每个零食的价值 v(i)，如果 FJ 以最优方式订购它们的销售，FJ 可以获得的最大价值是多少？

第一个零食在第 1 天售出，年龄 a=1。随后的每一天，年龄增加 1。

输入第 1 行：单个整数 N

第 2..N+1 行：第 i+1 行包含treat v(i) 的值

输出 FJ 可以通过出售零食获得的最大收入

示例输入：5

1 3 1 5 2

输出：43

在这个问题中 dp 的基本方法是什么？我如何处理 dp 矩阵中的年龄......？唯一让我想到的方法是递归方法...我是 DP 新手，我已经解决了一些基本的 dp 问题，但这超出了我的想法...这是我迄今为止尝试过的

int give(int a[],int x,int y,int age)
{

if(x==y) return age*a[x];

return max(age*a[x]+give(a,x+1,y,age+1),age*a[y]+give(a,x,y-1,age+1));

}

x=起始索引，从 0 初始化，y=最后索引，n-1，第一次调用时年龄=1

标签： c++dynamic-programming

解决方案

首先要观察的是，当前状态不取决于我们从哪里获取食物的历史。我们唯一关心的是我们从左边拿了多少次，从右边拿了多少次。

因此，状态可以只用 2 个数字进行编码：左偏移和右偏移。

假设f(i,j)我们在当前移动出售之前仍然可以获得的金额。我们知道我们已经i+j从线路中取出了对象，所以年龄也是i+j。

因此，我们只需要检查我们想从哪个位置开始，然后选择更好的位置。好吧，如果我们从左边挑选一个款待，我们获得的金额将是

cost * time + f( i + 1 , j ) = cost * (i + j) + f( i + 1 , j ).

如果我们从右边取的金额有一个非常相似的公式

cost_right * (i + j) + f( i , j + 1 ).

因此我们可以知道f(i+1,j)和f(i,j+1)计算f(i,j)。

这可以使用动态编程来完成，方法是存储一个 2D 大小的数组，n*n该数组存储-1iff(i,j)未知或f(x,y)if 已知的值。然后您可以简单地更新上述递归方法以实际存储结果并返回已知的解决方案。如果我们看一下您的代码示例，我们可以修改它以及时运行。

    int give(int a[],int x,int y,int age)
    {
        if(dp[x][y]!=-1) return dp[x][y];
        if(x==y) return age*a[x];

        int answer=max(age*a[x]+give(a,x+1,y,age+1),age*a[y]+give(a,x,y-1,age+1));

        dp[x][y]=answer;
        return answer;
    }

这只是一个片段，因为您需要修复边界条件并制作实际的全局 dp 数组，但我希望这足以开始。

推荐阅读