洛谷 P2858 奶牛零食

https://www.luogu.org/problemnew/show/P2858

毫无疑问区间dp。

！[区间dp入门]

我们定义dp[i][j]表示从i到j的最大收益，显然我们需要利用比较小的区间来推出更大的区间。

初始化dp[i][i]=单价，这里先不考虑第几天卖。

现在我们来确定小区间与大区间的关系，继而写出递推方程式。

每一个区间长度为一的块，想要扩大区间长度，那么只需要考虑对于现区间的左右端点的相邻点，我们可以通过比较确定是取左邻点还是右邻点(i，j分别表示左右端点)。

$$dp[i][j]=max(dp[i-1][j],dp[i][j-1])[i,j]$$

现在我们不管取左边的点还是右边的点，没有动过的点卖的天数县比与上一个状态晚卖了一天，所以每一个物品要加一次单价。

那么需要(a[k]表示单价)

$$dp[i][j]+=\sum_{k=i}^{k<=j}a[k]$$

为了简便$\sum_{k=i}^{k<=j} a[k]$提前用前缀和统计一下就好了。

所以外层循环枚举区间长度，内层循环枚举左端点。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <map>

using namespace std;

#define LL long long

#define mod int(1e9+7)

#define wlz 1234567890

int n,ans1,ans2;

int a[],sum[],dp[][];

int main()

{

//    cout<<sizeof(dp)/1024/1024;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        sum[i]=sum[i-]+a[i];

    }

    for(int i=n;i>=;i--)

    {

        for(int j=i;j<=n;j++)

        {

            dp[i][j]=max(dp[i+][j],dp[i][j-]);

            dp[i][j]+=(sum[j]-sum[i-]);

        }

    }

    printf("%d",dp[][n]);

}

巴特西

洛谷 P2858 奶牛零食

最新文章

热门文章