题目
点这里看题目。
分析
先特判掉(K=2)的情况。
首先可以考虑到一个简单 DP :
(f(i)):前(i)张牌的最大贡献。
转移可以(O(n^2))地枚举区间众数,但它不存在决策单调性,众数查询也很难优化。
考虑另一种转移。我们对于(f(i)),只取它结尾的点数的后缀
[f(i)=max_{1le jle i,a_j=a_i}{f(j-1)+s(i)-s(j)+1}
]
其中的(s_i)为前(i)张牌里与第(i)张点数相同的牌的张数。
这个转移从全局来看也不存在单调性,但实际上,它具有部分单调性:
对于所有的结尾点数相同的(f),除开(i=j)的转移,剩下的转移中它的最优决策点与前面的结尾点数相同的(f)的已有决策点是单调不增的。
利用好这个性质,我们就可以对于每个颜色维护一个(i
ot=j)的转移的单调栈,计算新的值的时候把已有的不优的决策点弹掉,插入新的值的时候二分一下右边界,时间是(O(nlog_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
", ( 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
", f[N] );
return 0;
}