P5124 Teamwork(DP)
2019-11-03 16:00:50来源:博客园 阅读 ()
P5124 Teamwork(DP)
题目:
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];
}
原文链接:https://www.cnblogs.com/lykkk/p/11785204.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C/C++中new的使用规则
下一篇:STL之string
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash