Link.
一种物品有 长度 和 权值 两种属性,现给定 \(n\) 组物品,第 \(i\) 组有 \(k_i\) 个,分别为 \((1,a_{i,1})..(k_i,a_{i,k_i})\),求在每组物品里恰好选择一个物品,且物品长度和恰为 \(i=n..\sum k\) 时的最大物品权值和。
\(n\le10^5\),\(k_i\le5\)。
本次 NOIP 模拟赛 考察的知识点包括但不限于:凸性函数的研究应用、闵可夫斯基和、Gale-Ryser 定理、LCT……是一套非常优秀的组题。
先令所有长度 \(-1\),长度区间变为 \([0,K=4]\)。考虑暴力 DP,令 \(f(i,j)\) 在前 \(i\) 组中选出长度和为 \(j\) 的物品时最大权值和。
结论:令 \(L=12\),\(f_{i,r}(x)=f(i,xL+r)~(r\in[0,L),x\in\mathbb N)\),则 \(f_{i,r}(x)\) 的图像是上凸的点集。
证明
承认这样一个结论:对于整数集 $A$,$\forall a\in A,a\in[0,4],\sum_{a\in A}=24$,则 $\exist B\subseteq A,\sum_{b\in B}b=12$。
作者水平有限,没有找到除暴搜和冗长分类讨论之外的简洁证明。且满足这一性质的常数值除 \(([0,4],24)\) 以外,还有许多分布规律不明显的解。有兴趣的读者欢迎一起讨论。
此后,考虑任意 \(f_{i,r}(x-1),f_{i,r}(x),f_{i,r}(x+1)\)。研究从 \(f_{i,r}(x-1)\) 的最优解调整得到 \(f_{i,r}(x+1)\) 最优解的过程,设第 \(j\) 组物品所选长度变化量为 \(\Delta_j\),可以看出 \(\Delta_j\in[-4,4]\),且 \(\sum\Delta_j=2L=24\)。我们能通过贪心的方式构造将 \(\Delta_j\) 分组,使得每组 \(\Delta_j\) 之和 \(\in[0,4]\),运用上文结论,得到两组长度变化量为 \(12\) 的调整方案 \(D_1,D_2\)。将其中权值变化量较大的一组作用在 \(f_{i,r}(x-1)\) 上可以得到 \(f_{i,r}(x)\) 的一个下界,即有 \(f_{i,r}(x)\ge\frac{f_{i,r}(x-1)+f_{i,r}(x+1)}{2}\),结合 \(x=\frac{(x-1)+(x+1)}{2}\),我们证明了两点中点在图像形成的多边形内,即,图像是(上)凸的。 \(\square\)
利用结论,分治 + 闵可夫斯基和求出函数 \(f_{n,0..L-1}\) 即可。复杂度 \(\mathcal O(LKn\log n)\)。
由于着急补题,直接套了计算几何的板子。针对凸性 DP 的高效归并可以看 OneInDark 的博客。
/*~Rainybunny~*/
#ifndef RYBY
#pragma GCC optimize( "Ofast" )
#endif
#include <bits/stdc++.h>
#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 char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && ( q = buf + fread( p = buf, 1, 1 << 17, stdin ), p == q )
? EOF : *p++;
}
inline int rint() {
int x = 0, s = fgc();
for ( ; s < '0' || '9' < s; s = fgc() );
for ( ; '0' <= s && s <= '9'; s = fgc() ) x = x * 10 + ( s ^ '0' );
return x;
}
inline void wint( const LL x ) {
if ( 9 < x ) wint( x / 10 );
putchar( x % 10 ^ '0' );
}
inline void chkmax( LL& u, const LL v ) { u < v && ( u = v ); }
const int MAXN = 1e5;
namespace PGP {
const double EPS = 1e-9, PI = acos( -1. );
inline int dcmp( const double a ) {
return -EPS < a && a < EPS ? 0 : a < 0 ? -1 : 1;
}
struct Point {
int x; LL y;
Point(): x( 0 ), y( 0 ) {}
Point( const int a, const LL b ): x( a ), y( b ) {}
inline Point operator + ( const Point& p ) const {
return { x + p.x, y + p.y };
}
inline Point operator - ( const Point& p ) const {
return { x - p.x, y - p.y };
}
inline LL operator ^ ( const Point& p ) const {
return x * p.y - y * p.x;
}
inline double angle() const {
double t = atan2( y, x );
return t < 0 ? t + 2 * PI : t;
}
};
typedef Point Vector;
typedef std::vector<Point> Convex;
inline Convex minkowskiSum( const Point& ap, const Point& bp,
const Convex& A, const Convex& B ) {
int n = int( A.size() ), m = int( B.size() );
static Convex ret; ret.clear(), ret.resize( n + m + 1 );
ret[0] = ap + bp;
int i = 0, j = 0, k = 0;
while ( i < n && j < m ) {
ret[k + 1] = ( ret[k] + ( ( A[i] ^ B[j] ) > 0 ? A[i++] : B[j++] ) );
++k;
}
while ( i < n ) ret[k + 1] = ret[k] + A[i++], ++k;
while ( j < m ) ret[k + 1] = ret[k] + B[j++], ++k;
return ret;
}
} using namespace PGP;
struct Atom {
std::vector<Point> f;
friend inline Atom operator + ( const Atom& u, const Atom& v ) {
static std::vector<Point> ur[12], vr[12]; static Atom ret;
static Point up[12], vp[12];
ret.f.clear(), ret.f.resize( u.f.size() + v.f.size() - 1 );
rep ( i, 0, int( ret.f.size() ) - 1 ) ret.f[i].x = i;
rep ( i, 0, 11 ) ur[i].clear(), vr[i].clear();
rep ( i, 0, int( u.f.size() ) - 1 ) ur[i % 12].push_back( u.f[i] );
rep ( i, 0, int( v.f.size() ) - 1 ) vr[i % 12].push_back( v.f[i] );
rep ( i, 0, 11 ) {
std::reverse( ur[i].begin(), ur[i].end() );
std::reverse( vr[i].begin(), vr[i].end() );
int n = int( ur[i].size() );
if ( n ) {
up[i] = ur[i][0];
rep ( j, 0, n - 2 ) ur[i][j] = ur[i][j + 1] - ur[i][j];
ur[i][n - 1] = up[i] - ur[i][n - 1];
}
n = int( vr[i].size() );
if ( n ) {
vp[i] = vr[i][0];
rep ( j, 0, n - 2 ) vr[i][j] = vr[i][j + 1] - vr[i][j];
vr[i][n - 1] = vp[i] - vr[i][n - 1];
}
}
rep ( i, 0, 11 ) if ( !ur[i].empty() ) {
rep ( j, 0, 11 ) if ( !vr[j].empty() ) {
const auto&& cvx( minkowskiSum( up[i], vp[j], ur[i], vr[j] ) );
for ( size_t k = 0; k < cvx.size(); ++k ) {
chkmax( ret.f[cvx[k].x].y, cvx[k].y );
}
}
}
return ret;
}
};
inline Atom solve( const int l, const int r ) {
if ( l == r ) {
int k = rint(), v;
static Atom ret; ret.f.resize( k );
rep ( i, 1, k ) ret.f[i - 1] = { i - 1, rint() };
return ret;
}
int mid = l + r >> 1;
const Atom &&u( solve( l, mid ) ), &&v( solve( mid + 1, r ) );
return u + v;
}
int main() {
freopen( "fake.in", "r", stdin );
freopen( "fake.out", "w", stdout );
const Atom&& ans( solve( 1, rint() ) );
for ( const auto& u: ans.f ) wint( u.y ), putchar( ' ' );
putchar( '\n' );
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章