题解 [SBCOI2020] 一直在你身旁
2024-08-30 06:55:09
题目大意
给出一个长度为 \(n\) 的单调不减的序列,每次可以选出一个点,产生贡献 \(a_k\),我们可以得知我们需要找到的数是否大于 \(k\)。问找到要找到的数最小花费。
\(n\le 7100\)
思路
\(\Theta(n^3)\) 的 \(\text{dp}\) 显然,可以设 \(f_{l,r}\) 表示答案在 \([l,r]\) 区间时找到答案最小贡献。可以得到转移式:
\[f_{l,r}=\min_{l\le k\le r}\{\max(f_{l,k},f_{k+1,r})+a_k\}
\]
\]
然后我们经过思考,发现以下事情:
\(f(l,r)\ge f(l,r-1),f(l,r)\ge f(l+1,r)\)
我们如果设 \(w_{l,r}\) 表示第一个满足 \(f_{l,k}\ge f_{k+1,r}\) 的 \(k\),那么可以发现对于相同的 \(r\),\(w_{l,r}\) 随着 \(l\) 的减小而减小。
于是,我们可以把问题拆成两个部分进行考虑。
- \(k< w_{l,r}\)
对于这一部分,我们观察到式子可以改写为:
\[f_{l,r}=\min_{l\le k<w_{l,r}}\{f_{k+1,r}+a_k\}
\]
\]
然后你发现这个式子可以使用单调队列进行优化。
- \(k\ge w_{l,r}\)
对于这一部分你发现式子可以改写为:
\[f_{l,r}=\min_{w_{l,r}\le k\le r}\{f_{l,k}+a_k\}
\]
\]
然后你发现 \(f_{l,k}+a_k\) 随着 \(k\) 的增大而增大,所以最优贡献点一定是在 \(w_{l,r}\)。
综上,可以枚举 \(r\) 然后使用单调队列优化即可,时间复杂度 \(\Theta(n^2)\)。
\(\texttt{Code}\)
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define int long long
#define MAXN 7105
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,head,tail,a[MAXN],q[MAXN],f[MAXN][MAXN];
void ins (int k,int r){
while (head <= tail && f[r][q[tail] + 1] + a[q[tail]] >= f[r][k + 1] + a[k]) -- tail;
q[++ tail] = k;
}
signed main(){
int T;read (T);
while (T --> 0){
read (n);
for (Int i = 1;i <= n;++ i) read (a[i]);
for (Int r = 2;r <= n;++ r){
q[head = tail = 1] = r - 1,f[r][r - 1] = a[r - 1];int res = r;
for (Int l = r - 2;l >= 1;-- l){
while (f[res - 1][l] > f[r][res] && res > l) -- res;
while (head <= tail && q[head] >= res) ++ head;
f[r][l] = f[res][l] + a[res];
if (head <= tail) f[r][l] = min (f[r][l],f[r][q[head] + 1] + a[q[head]]);
ins (l,r);
}
}
write (f[n][1]),putchar ('\n');
}
return 0;
}
最新文章
- android shape的使用(转)
- Linux Shell 01 脚本与变量
- .net架构设计读书笔记--第三章 第10节 命令职责分离(CQRS)简介(Introducing CQRS)
- SPOJ #11 Factorial
- 在windows下用eclipse + pydev插件来配置python的开发环境
- Codeforces 161 B. Discounts (贪心)
- OpenSSL重大漏洞-Heartbleed之漏洞利用脚本POC讲解
- IIS配置 Web部署 svg/woff/woff2字体 404错误
- 网络通信TCP编程实例代码
- gulp折腾日记——gulp-livereload
- C#:求100到200之前所有的质数和
- linux文件 特殊权限的使用
- 13.缓存、三级缓存、内存溢出、AsyncTask
- 4.6Python多版本存在问题
- LaTeX语法笔记
- ubuntu server 启用mysql日志
- Docker命令分类及使用场景分布(脑图)
- 企业应用:C/S 开发需要考虑的事项
- jquery.fn.extend() 与 $.jquery 作用及区别
- 基于腾讯云CLB实现K8S v1.10.1集群高可用+负载均衡