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[ ......
题目:
解析:
动态规划,设\(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]; }
上一篇: PHP开发提高效率技巧
下一篇: 自定义日历(四)-区间选择控件
推荐阅读
-
Codeforces Round #275 (Div. 1)D(树形DP)_html/css_WEB-ITnose
-
树形DP图画入门题解2 (HDU2196)
-
蓝桥杯--砝码称重(dp)
-
Codeforces Round #157 (Div. 1) C. Little Elephant and LCM (数学、dp)
-
codeforces 607B Zuma 区间dp
-
[多维DP] 洛谷P1855 榨取kkksc03(简单加维)
-
【HDU - 2571】命运(DP动态规划)
-
动态规划入门之dp递推~
-
[线性DP] 洛谷P1387 最大正方形(思维定势问题)
-
Prince and Princess_dp