Solution -「ZJOI 2020」「洛谷 P6631」序列
2021/6/25 23:27:38
本文主要是介绍Solution -「ZJOI 2020」「洛谷 P6631」序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\(\mathcal{Description}\)
Link.
给定一个长为 \(n\) 的非负整数序列 \(\lang a_n\rang\),你可以进行如下操作:
- 取 \([l,r]\),将其中所有 \(a\) 值 \(-1\);
- 取 \([l,r]\),将其中奇数下标的 \(a\) 值 \(-1\);
- 取 \([l,r]\),将其中偶数下标的 \(a\) 值 \(-1\)。
求至少需要几次操作使得所有 \(a\) 值变为 \(0\)。
\(n\le10^5\),数据组数 \(T\le10\)。
\(\mathcal{Solution}\)
道路铺设永放光芒!
记集族 \(\mathcal I\) 包括所有一次操作可能涉及的下标集合,写出线规
\[\operatorname{minimize}~~~~z=\sum_{P\in \mathcal I}x_P\\ \operatorname{s.t.} \begin{cases} \forall u,~\sum_{P\ni u}x_P\ge a_u\\ \forall u,~-\sum_{P\ni u}x_P\ge -a_u\\ \forall P,~x_P\ge 0 \end{cases} \]转对偶
\[\operatorname{maximize}~~~~z'=\sum_{u=1}^na_u(s_u-t_u)\\ \operatorname{s.t.}\begin{cases} \forall P,~\sum_{u\in P}(s_u-t_i)\le1\\ \forall u,~s_u,t_u\ge0 \end{cases} \]令 \(d_u=s_u−t_u\),由第一个约束,显然有 \(d_u\le1\);而为最大化 \(\sum_{u=1}^na_ud_u\),可以得到 \(d_u\in\{-1,0,1\}\)。那么就能简单 DP:令 \(f(i,x,y,z)\) 表示考虑了 \(d_{1..i}\),一类/二类/三类操作涉及的操作集合中,最大后缀 \(d\) 之和为 \(x/y/z~(\in\{0,1\})\),枚举 \(d_u=1,2,3\) 分别转移即可。
复杂度 \(\mathcal O(Tn)\)(其实带一个 \(\ge \log n\) 的 \(24\) 倍常数 qwq)。
\(\mathcal{Code}\)
/*~Rainybunny~*/ #include <cstdio> #include <cstring> #define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i ) #define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i ) typedef long long LL; inline int rint() { int x = 0, f = 1, s = getchar(); for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f; for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' ); return x * f; } template<typename Tp> inline void wint( Tp x ) { if ( x < 0 ) putchar( '-' ), x = -x; if ( 9 < x ) wint( x / 10 ); putchar( x % 10 ^ '0' ); } template<typename Tp> inline void chkmax( Tp& a, const Tp& b ) { a < b && ( a = b, 0 ); } inline int imax( const int a, const int b ) { return a < b ? b : a; } const int MAXN = 1e5; const LL LINF = 1ll << 60; int n, a[MAXN + 5]; LL f[MAXN + 5][2][2][2]; int main() { for ( int T = rint(); T--; ) { n = rint(); rep ( i, 1, n ) a[i] = rint(); memset( f, 0xc0, sizeof f ); f[0][0][0][0] = 0; rep ( i, 1, n ) rep ( w, -1, 1 ) { rep ( x, 0, 1 ) rep ( y, 0, 1 ) rep ( z, 0, 1 ) { if ( w + x <= 1 && w + ( i & 1 ? y : z ) <= 1 ) { chkmax( f[i][imax( imax( w, w + x ), 0 )] [i & 1 ? imax( imax( w, w + y ), 0 ) : y] [i & 1 ? z : imax( imax( w, w + z ), 0 )], f[i - 1][x][y][z] + w * a[i] ); } } } LL ans = -LINF; rep ( x, 0, 1 ) rep ( y, 0, 1 ) rep ( z, 0, 1 ) { chkmax( ans, f[n][x][y][z] ); } wint( ans ), putchar( '\n' ); } return 0; }
这篇关于Solution -「ZJOI 2020」「洛谷 P6631」序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行