G - Pictures with Kittens (easy version) dp

https://codeforces.com/problemset/problem/1077/F1

这个其实是一个比较简单的dp了

题目大意：

给你n个数，让你从n个数里选出x个数，并且每隔k个至少选一个数。

开始不知道怎么去写，也不知道怎么去定义dp

这个应该是对于dp不是特别的熟练，实际上dp用途很广，而且可以用到的地方很多，效果也很好。

这种时候就应该大胆一点，你需要什么，想达成什么效果那就去这样定义。

这个题目，我们希望dp可以帮我们解决前面n个数，选了x个数的最大和，而且这个还必须每隔k就选择了一个数。

这个是大问题，子问题是什么呢？

如果我们选第i个数，那么前面n-1个数，选了x-1个数的最大和。。。。

否则就是我们不选第i个数，那么前面n-1个数，选了x个数的最大和。 ----这种情况我们最多可以向前面推k-1次

所以我们要怎么定义呢？

首先要有一维来记录到第几个数了，还有一维就是要记录我们选了多少个了，

两维记录可以唯一确定每一个状态，所以两维就够了

那到底怎么去定义这个dp呢？dp的含义是什么呢？

这个我觉得不是很好想。

dp[i][j]表示前面i个数，已经选了j个数的最大和吗？

但是因为这个有区间限制，就是每隔k就必须有一个数，所以这个时候我们就要确定前面的那个值的位置，

所以我们就定义为已经选择了第i个数，前面i个数选了j个数的最大和。

状态定义好了之后，就是转移方程的确定了。

dp[i][j]=max(dp[i][j],dp[s][j-1]+a[i])

这个s其实就是i往前推，然后去最大值，所以需要三维。

而且这个往前推最多推k个数。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = ;

typedef long long ll;

ll dp[ * maxn][ * maxn];

ll a[maxn];

int main()

{

    int n, k, x;

    scanf("%d%d%d", &n, &k, &x);

    for (int i = ; i <= n; i++) scanf("%lld", &a[i]);

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

    {

        for(int j=;j<=x;j++)

        {

            dp[i][j] = -inf;

        }

    }

    dp[][] = ;

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

    {

        for(int j=;j<=x;j++)

        {

            for(int h=;h<=k&&h<=i;h++)

            {

                if (dp[i - h][j - ] == -inf) continue;

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

            //    printf("dp[%d][%d]=%lld\n", i, j, dp[i][j]);

            }

        }

    }

    ll ans = -inf;

    for (int i = n - k + ; i <= n; i++) ans = max(ans, dp[i][x]);

    if (ans < ) printf("-1\n");

    else printf("%lld\n", ans);

    return ;

}

线性dp

巴特西

G - Pictures with Kittens (easy version) dp

最新文章

热门文章