题目

分析

先特判掉\(K=2\)的情况。

首先可以考虑到一个简单 DP ：

\(f(i)\)：前\(i\)张牌的最大贡献。

转移可以\(O(n^2)\)地枚举区间众数，但它不存在决策单调性，众数查询也很难优化。

考虑另一种转移。我们对于\(f(i)\)，只取它结尾的点数的后缀

\[f(i)=\max_{1\le j\le i,a_j=a_i}\{f(j-1)+s(i)-s(j)+1\}
\]

其中的\(s_i\)为前\(i\)张牌里与第\(i\)张点数相同的牌的张数。

这个转移从全局来看也不存在单调性，但实际上，它具有部分单调性：

对于所有的结尾点数相同的\(f\)，除开\(i=j\)的转移，剩下的转移中它的最优决策点与前面的结尾点数相同的\(f\)的已有决策点是单调不增的。

利用好这个性质，我们就可以对于每个颜色维护一个\(i\not=j\)的转移的单调栈，计算新的值的时候把已有的不优的决策点弹掉，插入新的值的时候二分一下右边界，时间是\(O(n\log_2n)\)。

代码

#include <cmath>

#include <cstdio>

#include <vector>

using namespace std;

const int MAXN = 1e6 + 5;

template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}

template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}

template<typename _T>

_T MAX( const _T a, const _T b )

{

	return a > b ? a : b;

}

vector<int> pos[MAXN];

double pw[MAXN], f[MAXN];

int stk[MAXN], but[MAXN], top[MAXN], rig[MAXN];

int A[MAXN], pre[MAXN], tot[MAXN], vised[MAXN];

int N, K;

double getDP( const int i, const int j )

{

	return f[j - 1] + pw[pre[i] - pre[j] + 1];

}

int get( const int i, const int j )

{

	int id = A[i];

	int l = vised[id] - 1, r = pos[id].size() - 1, mid;

	while( r - l > 1 )

	{

		mid = l + r >> 1;

		if( getDP( pos[id][mid], i ) >= getDP( pos[id][mid], j ) ) l = mid;

		else r = mid - 1;

	}

	if( getDP( pos[id][r], i ) >= getDP( pos[id][r], j ) ) return pos[id][r];

	return pos[id][l];

}

int main()

{

	read( K ), read( N );

	for( int i = 1 ; i <= N ; i ++ ) pw[i] = pow( i, 1.0 * K / 2 );

	for( int i = 1 ; i <= N ; i ++ ) read( A[i] ), pre[i] = ++ tot[A[i]], pos[A[i]].push_back( i );

	if( K == 2 ) { printf( "%.10lf\n", ( double ) N ); return 0; }

	int siz = 0;

	for( int i = 1 ; i <= N ; i ++ )

		if( tot[i] )

			but[i] = siz + 1, top[i] = siz, siz += tot[i];

	int id;

	for( int i = 1 ; i <= N ; i ++ )

	{

		f[i] = f[i - 1] + 1, id = A[i];

		while( but[id] < top[id] && i > rig[top[id] - 1] ) top[id] --;

		if( but[id] <= top[id] ) f[i] = MAX( f[i], getDP( i, stk[top[id]] ) );

		while( but[id] < top[id] && get( i, stk[top[id]] ) >= rig[top[id] - 1] ) top[id] --;

		if( but[id] <= top[id] ) rig[top[id]] = get( i, stk[top[id]] );

		stk[++ top[id]] = i, rig[top[id]] = N;

		vised[id] ++;

	}

	printf( "%.10lf\n", f[N] );

	return 0;

}

巴特西

[noi.ac省选模拟赛20200606]赌怪

题目

分析

代码

最新文章

热门文章