Description
一个序列,每次可以将两个相同的数合成一个数,价值+1,求最后最大价值 \(n \leqslant 262144\)
Sol
DP.
这道题是 BZOJ 4580: [Usaco2016 Open]248 加强版.
做248的那个区间DP其实很多方案都是0,而且一个区间中只有一个合法的数字.
然后就是 一个区间合成一个数的方案的这个数字是固定的.
\(f[i][j]\) 表示以 \(i\) 结尾是否能合成 \(j\),同时记录一下转移位置,每次向前找前一个指针就可以了.
复杂度 \(O(nm)\)
Code
/**************************************************************
Problem: 4576
User: BeiYu
Language: C++
Result: Accepted
Time:1208 ms
Memory:79368 kb
****************************************************************/ #include <cstdio>
#include <iostream>
using namespace std; const int N = 263005;
const int M = 60; int n,ans,a[N];
bool f[N][M];int g[N][M]; inline int in(int x=0){ scanf("%d",&x);return x; }
int main(){
n=in();
for(int i=1;i<=n;i++) a[i]=in();
for(int i=1,p;i<=n;i++){
p=i-1,f[i][a[i]]=1,g[i][a[i]]=i;
ans=max(ans,a[i]);
for(int j=a[i];j<M;j++){
if(f[p][j]) f[i][j+1]=1,g[i][j+1]=g[p][j],p=g[p][j]-1,ans=max(ans,j+1);
else break;
}
}
// for(int i=1;i<=n;i++) for(int j=1;j<6;j++) cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<g[i][j]<<endl;
cout<<ans<<endl;
return 0;
}