『optimization 动态规划』
2024-09-08 11:15:18
<更新提示>
<第一次更新>
<正文>
optimization
Description
\(visit\_world\) 发现有些优化问题可以用很平凡的技巧解决,所以他给你分享了这样一道题:
现在有一个长度为N的整数序列\(\{a_i\}\) ,你需要从中选出K个不相交的连续子区间(可以存在元素不被选),从左到右记它们的和为\(s1,s2,...,sk\)。我们的优化目标是最大化下述和式:
\[\sum_{i=1}^k|s_i−s_{i+1}|
\]
\]
你只需要输出这个最大的和即可.
Input Format
第一行两个整数N,K,意义如上.
接下来一行N个整数,第i个数表示ai,保证有\(|a_i|≤10^4\) .
Output Format
输出一行一个整数,表示答案.
Sample Input
5 3
5 2 4 3 1
Sample Output
12
解析
一道很神奇的\(dp\)。
关于绝对值的最大和,一个小\(trick\)就是拆开绝对值号,对正负两种情况都\(dp\),最后去最大值一定就是最优解。
那么我们发现对于一个\(s_i\),他可能有三种贡献系数:\(2,-2,0\),这与\(s_{i-1},s_{i+1}\)与其的相对大小关系有关,当然,对于\(s_1,s_k\),他们的贡献系数还有可能是\(1,-1\),我们不妨由此设计状态。
设\(f[i][j][0/1/2/3]\)代表前\(i\)个数,分成\(j\)段,当前处于最大值(\(+2\)贡献),最小值(\(-2\)贡献),上升状态(\(0\)贡献),下降状态(\(0\)贡献)的最大和。其中上升状态和下降状态指的就是最大值和最小值前的一些\(0\)贡献的状态。
然后就可以\(dp\)了,时间复杂度是\(O(n^3k)\)的。
考虑优化,第一个就是我们可以强制认为每一个数字都是要取的,当然不取可以放在\(0\)贡献的状态里处理。第二个每一段当中的数字贡献系数的相同的,可以直接一个一个添加数字。
\(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4+20 , K = 220 , INF = 0x3f3f3f3f;
inline int read(void)
{
int x = 0 , w = 0; char ch = ' ';
while ( !isdigit(ch) ) w |= ch == '-' , ch = getchar();
while ( isdigit(ch) ) x = x * 10 + ch - 48 , ch = getchar();
return w ? -x : x;
}
int n,k,a[N],f[N][K][4];
inline void input(void)
{
n = read() , k = read();
for (int i=1;i<=n;i++)
a[i] = read();
}
inline void dp(void)
{
memset( f , 0xcf , sizeof f );
for (int i=1;i<=n;i++)
f[i][0][0] = f[i][0][1] = f[i][0][2] = f[i][0][3] = 0;
f[0][0][0] = f[0][0][1] = f[0][0][2] = f[0][0][3] = 0;
for (int i=1;i<=n;i++)
for (int j=1;j<=min(i,k);j++)
{
int mul = 2;
if ( j == 1 || j == k ) mul--;
f[i][j][0] = max( f[i-1][j][0] , f[i-1][j-1][2] ) + mul * a[i];
f[i][j][1] = max( f[i-1][j][1] , f[i-1][j-1][3] ) - mul * a[i];
f[i][j][2] = max( f[i-1][j][2] , f[i][j][1] );
f[i][j][3] = max( f[i-1][j][3] , f[i][j][0] );
if ( mul == 1 ) continue;
f[i][j][2] = max( f[i][j][2] , f[i-1][j-1][2] );
f[i][j][3] = max( f[i][j][3] , f[i-1][j-1][3] );
}
}
int main(void)
{
input();
dp();
printf("%d\n",max(f[n][k][2],f[n][k][3]));
return 0;
}
<后记>
最新文章
- VS2015常用快捷键总结
- EditView 输入限制(软键盘限制)
- HDU 1561 树形DP入门
- 我的web框架
- Rigidbody SweepTest测试
- 正则表达式(BREs,EREs,PREs)差异比较
- 2015网易校招Java开发工程师(技术架构)在线笔试题
- 使用CocoaPods找不到头文件解决方法
- java-多线程安全问题
- javascript/jquery读取和修改HTTP headers
- JS 一些常用技巧
- HTTPS介绍
- webstorm 设置uglify 压缩js文件
- git服务搭建以及本地连接
- 在JSON中遇到的一些坑
- Matlab-11:Gausssidel迭代法工具箱
- Spring Boot 揭秘与实战(九) 应用监控篇 - HTTP 应用监控
- 正则grep
- [转]redhat7(centos7) not registered to Red Hat Subscription Management
- java获取路径(转)
热门文章
- WinRAR命令行版本 rar.exe使用详解(适用Linux)
- 最新版windows安装支持输入shell命令的工具cygwin教程
- 相同域名下的cookie污染
- skipped obstructing working copy
- vnc服务器和windows2012密钥
- plotly 安装
- 关于如何自定义修改pytest-html报告深度学习总结
- pipenv安装包时一直卡在Locking [packages] dependencies…,换pypi源
- 如何隐藏WooCommerce Shop Page页面的标题
- 柯里化currying + 隐式调用 = 一个有名的add面试题