欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P5124 Teamwork(DP)

程序员文章站 2022-05-22 16:52:56
题目: "P5124 [USACO18DEC]Teamwork" 解析: 动态规划,设$f[i]$表示到第$i$位的最大值,我们枚举i之前的j个位置$(j using namespace std; const int N = 1e6 + 10; int n, m, num; int a[N], f[ ......

题目:

p5124 [usaco18dec]teamwork

解析:

动态规划,设\(f[i]\)表示到第\(i\)位的最大值,我们枚举i之前的j个位置\((j<k)\),记录一下这\(j+1\)个数(包括自己)的最大值\(mx\),转移方程就是\(f[i]=max(f[i],f[i-j-1]+mx\times (j+1))\)

代码:

#include <bits/stdc++.h>
using namespace std;

const int n = 1e6 + 10;

int n, m, num;
int a[n], f[n];

template<class t>void read(t &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) {
        int mx = -1;
        f[i] = f[i - 1] + a[i];
        for (int j = 0; j < m && i - j > 0; ++j) {
            mx = max(mx, a[i - j]);
            f[i] = max(f[i], f[i - j - 1] + mx * (j + 1));
        }
    }
    cout << f[n];
}