Prob. 1
暴力为 $\Theta(NK)$。
正解（也许）：
把每一个全为正整数的子段找出来。
然后判断一下中间连接的情况即可。
但是这样决策情况太多了。
我们需要考虑贪心。
把所有整数段的个数记为 $totP$，每个子段的区间记为 $[posL_{i},posR_{i}]$，区间和记为 $sumP_{i}$
把其他的负数段个数记为 $totN$，区间和记为 $sumN_{i}$。
当 $totP\le k$ 答案显然。
我们需要考虑的是 $totP>k$ 的情况。
我们把整数段、负数段缩成点。
然后问题还是最多选 $k$ 段的最大子段和。
不过我们的序列有个性质：相邻数的正负性不同。（gu）
好了放弃以上想法。
模拟 $k$ 轮找全局最大子段和，找到一次把子段乘上 $-1$。
#include <cstdio>
typedef long long LL;
const int MAXN = 1e5 + 5;
int rint () {
int x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T>
void wint ( _T x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }
template<typename _T> void swapp ( _T &x, _T &y ) { _T w = x; x = y; y = w; }
struct nodeS {
LL val, dat, p, s;
int l, r, pl, pr, sl, sr;
nodeS ( LL V = 0, LL D = 0, LL P = 0, LL S = 0,
int L = 0, int R = 0, int Pl = 0, int Pr = 0, int Sl = 0, int Sr = 0 ) {
val = V, dat = D, p = P, s = S, l = L, r = R, pl = Pl, pr = Pr, sl = Sl, sr = Sr; }
} nodes[MAXN * 4][2];
int n, k, a[MAXN];
bool tag[MAXN * 4];
nodeS Merge ( const nodeS lch, const nodeS rch ) {
nodeS ret;
ret.val = lch.val + rch.val;
ret.p = MAX ( lch.p, lch.val + rch.p );
if ( ret.p == lch.p ) ret.pl = lch.pl, ret.pr = lch.pr;
else ret.pl = lch.pl, ret.pr = rch.pr;
ret.s = MAX ( rch.s, rch.val + lch.s );
if ( ret.s == rch.s ) ret.sl = rch.sl, ret.sr = rch.sr;
else ret.sl = lch.sl, ret.sr = rch.sr;
ret.dat = MAX ( lch.s + rch.p, MAX ( lch.dat, rch.dat ) );
if ( ret.dat == lch.dat ) ret.l = lch.l, ret.r = lch.r;
else if ( ret.dat == rch.dat ) ret.l = rch.l, ret.r = rch.r;
else ret.l = lch.sl, ret.r = rch.pr;
return ret;
}
void Upt ( const int x ) {
nodes[x][0] = Merge ( nodes[x << 1][0], nodes[x << 1 | 1][0] );
nodes[x][1] = Merge ( nodes[x << 1][1], nodes[x << 1 | 1][1] );
}
void Spr ( const int x ) {
if ( ! tag[x] ) return;
swapp ( nodes[x << 1][0], nodes[x << 1][1] );
swapp ( nodes[x << 1 | 1][0], nodes[x << 1 | 1][1] );
tag[x << 1] ^= 1, tag[x << 1 | 1] ^= 1, tag[x] = 0;
}
void Build ( const int x, const int l, const int r ) {
if ( l == r ) {
nodes[x][0] = nodeS ( a[l], a[l], a[l], a[l], l, l, l, l, l, l );
nodes[x][1] = nodeS ( -a[l], -a[l], -a[l], -a[l], l, l, l, l, l, l );
return;
}
int mid = ( l + r ) >> 1;
Build ( x << 1, l, mid );
Build ( x << 1 | 1, mid + 1, r );
Upt ( x );
}
void Modify ( const int x, const int l, const int r, const int segL, const int segR ) {
if ( l > segR || r < segL ) return;
if ( l >= segL && r <= segR ) {
swapp ( nodes[x][0], nodes[x][1] );
tag[x] ^= 1;
return;
}
int mid = ( l + r ) >> 1;
Spr ( x );
Modify ( x << 1, l, mid, segL, segR );
Modify ( x << 1 | 1, mid + 1, r, segL, segR );
Upt ( x );
}
int main () {
n = rint (), k = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = rint ();
Build ( 1, 1, n );
LL ans = 0;
while ( k -- > 0 ) {
nodeS ret = nodes[1][0];
if ( ret.dat < 0 ) break;
Modify ( 1, 1, n, ret.l, ret.r );
ans += ret.dat;
}
wint ( ans ), putchar ( '\n' );
return 0;
}Prob. 2
设 $f_{i,0/1}$ 表示把 $a_{i}$ 往头/尾放可以得到的最多的上升子序列。
$$ f_{i,0}=\begin{cases}\max\{f_{j,0},f_{j,1}\}+1,a_{i}<a_{j} \\\max\{f_{j,0},f_{j,1}\},a_{i}\ge a_{j}\end{cases} \\f_{i,1}=\begin{cases}\max\{f_{j,0},f_{j,1}\},a_{i}<a_{j} \\\max\{f_{j,0},f_{j,1}\}+1,a_{i}\ge a_{j}\end{cases} $$
不行。
考虑普通的 LIS 怎么做。
$$ f_{i}=\max\{f_{j}\}+1,a_{i}>a_{j} $$
$$ a_{i}<a_{j},i<j $$
选择往前放的元素，放得越晚越靠前。
选择往后放的元素，放得越晚越靠后。
那么需要做的是把相对较大的元素往后，相对较小的元素往前。
连边，把李三花后的 $a_{i}$ 连向 $\text{trans}(i,0),\text{trans}(i,1),\text{trans}(x,0/1)=n-x+1/x+n$。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
int rint () {
int x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T>
void wint ( _T x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }
struct Value {
int val, pos;
Value ( int V = 0, int P = 0 ) { val = V, pos = P; }
bool operator < ( const Value &another ) { return val < another.val; }
} vals[MAXN];
struct GraphSet {
int to, nx;
GraphSet ( int T = 0, int N = 0 ) { to = T, nx = N; }
} as[MAXN * 2];
int n, cnt, len, degin[MAXN], a[MAXN], b[MAXN], buc[MAXN], sywf[MAXN];
void makeEdge ( const int u, const int v ) { as[++ cnt] = GraphSet ( v, degin[u] ), degin[u] = cnt; }
int Trans ( const int x, const int y ) { return ! y ? n - x + 1 : x + n; }
void ADD ( int p, const int x ) { for ( ; p <= ( n << 1 ); p += p & -p ) sywf[p] = MAX ( sywf[p], x ); }
int ASK ( int p ) { int res = 0; for ( ; p; p -= p & -p ) res = MAX ( res, sywf[p] ); return res; }
int CMP ( const int x, const int y ) { return x > y; }
int main () {
// freopen ( "dequexlis.in", "r", stdin );
// freopen ( "dequexlis.out", "w", stdout );
n = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = b[i] = rint ();
sort ( b + 1, b + 1 + n );
len = unique ( b + 1, b + 1 + n ) - b - 1;
for ( int i = 1; i <= n; ++ i ) a[i] = lower_bound ( b + 1, b + 1 + len, a[i] ) - b;
for ( int i = 1; i <= n; ++ i ) vals[i] = Value ( a[i], i );
for ( int i = 1; i <= n; ++ i ) {
makeEdge ( a[i], Trans ( i, 0 ) );
makeEdge ( a[i], Trans ( i, 1 ) );
}
int BUC = 0;
for ( int x_x = 1; x_x <= n; ++ x_x ) {
int u = x_x;
BUC = 0;
for ( int i = degin[u]; i; i = as[i].nx ) {
int v = as[i].to;
buc[++ BUC] = v;
}
sort ( buc + 1, buc + 1 + BUC, CMP );
for ( int i = 1; i <= BUC; ++ i ) ADD ( buc[i], 1 + ASK ( buc[i] - 1 ) );
}
wint ( ASK ( n << 1 ) ), putchar ( '\n' );
return 0;
}
/* Jesus bless all */Prob. 3
放弃人生打了个 50 的记搜。
#include <cstdio>
#include <map>
#define mod ( 998244853 )
using namespace std;
template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }
int n, m;
namespace Course {
const int MAXN = 255;
int f[MAXN][MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN];
int dfs ( const int mx, const int a, const int b ) {
if ( vis[a][b][mx] ) return f[a][b][mx];
vis[a][b][mx] = 1;
if ( a == n && b == m ) return f[a][b][mx] = mx;
if ( a < n ) f[a][b][mx] = ( f[a][b][mx] + dfs ( MAX ( mx, a - b + 1 ), a + 1, b ) ) % mod;
if ( b < m ) f[a][b][mx] = ( f[a][b][mx] + dfs ( mx, a, b + 1 ) ) % mod;
return f[a][b][mx];
}
}
int main () {
// freopen ( "maxpsum.in", "r", stdin );
// freopen ( "maxpsum.out", "w", stdout );
scanf ( "%d%d", &n, &m );
if ( n <= 250 && m <= 250 ) printf ( "%d\n", Course :: dfs ( 0, 0, 0 ) );
// else printf ( "%d\n", Might :: dfs ( 0, 0, 0 ) );
return 0;
}