频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
NOI2015 后缀自动机+DP
2017-02-11 09:50:00         来源:INCINCIBLE的博客  
收藏   我要投稿

NOI2015 后缀自动机+DP:很显然可以用后缀自动机来搞。将输入的字符串翻转,构造SAM。对每一个节点x,求出:(1)子树中 满足LCA(u,v)==x 的点对 的对数,(2)子树中 满足LCA(u,v)==x 的点对 的美味值乘积最大值。注意最大值有可能由两个最小的负数相乘得到。

所以最大、最小值都要记。最后的答案为ans1[],ans2[],如果节点x表示的最长子串长度为Max,那么x的答案可以更新ans1[Max],ans2[Max].注意数据范围,INF要足够大。

代码:

#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int maxn=600000+5;
const LL inf= 1000000000000000000LL+5LL;

int tot=1,last=1,n,x[maxn],dfn[maxn];
LL A[maxn], ans1[maxn],ans2[maxn];
char s[maxn];

struct node{
    int Next[26];
    int Max,pre;
    LL maxv,minv,cnt,multi,size;
    // maxv,minv表示子树中美味值得最大、最小值
    // cnt 表示有多少对 节点(u,v)满足LCA(u,v)为当前节点.
    //multi 表示满足条件的 (u,v)的最大美味值。 
}T[maxn];

template 
inline void _read(T &x){
    char ch=getchar(); bool mark=false;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')mark=true;
    for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    if(mark)x=-x;
}

void Insert(int x){
    int id= s[x]-'a';
    int np= ++tot,cur=last;
    T[np].Max=T[last].Max+1; T[np].size=1;
    T[np].maxv=T[np].minv=A[x];
    T[np].multi =-inf; 
    while(cur){
        if(!T[cur].Next[id])  T[cur].Next[id]= np;
        else {
            int v= T[cur].Next[id];
            if(T[v].Max==T[cur].Max+1) T[np].pre=v;
            else{
                int nq= ++tot;
                memcpy(T[nq].Next,T[v].Next,sizeof(T[v].Next));
                T[nq].maxv=T[nq].multi= -inf;
                T[nq].minv= inf;
                T[nq].Max=T[cur].Max+1;
                T[nq].pre=T[v].pre; 

                T[np].pre= nq; T[v].pre= nq; 
                for(int i= cur;T[i].Next[id]==v;i=T[i].pre)
                    T[i].Next[id]=nq;
            } 
            break;
        }
        cur=T[cur].pre;
    }
    if(!T[np].pre)T[np].pre=1;
    last=np;
}

void TreeDP(){
    int i,j;
    T[0].multi=T[1].maxv=T[1].multi= -inf; T[1].minv= inf;
    for(i=1;i<=tot;i++)x[T[i].Max]++;
    for(i=1;i<=n;i++) x[i]+=x[i-1];
    for(i=1;i<=tot;i++) dfn[x[T[i].Max]--]= i;
    for(i=tot;i>0;i--){   //深度由深到浅 DP
        int cur= dfn[i],fa=T[cur].pre;
        T[fa].cnt+= T[fa].size*T[cur].size;
        T[fa].size+= T[cur].size;
        if(T[fa].maxv!= -inf) T[fa].multi= max(T[fa].multi,T[fa].maxv*T[cur].maxv);
        if(T[fa].minv!= inf)  T[fa].multi= max(T[fa].multi,T[fa].minv*T[cur].minv); 
        //这里不判断乘法会溢出 
        T[fa].maxv=max(T[fa].maxv,T[cur].maxv);
        T[fa].minv=min(T[fa].minv,T[cur].minv);
    }
} 

int main(){
    int i,j;
    _read(n);
    scanf("%s",s+1);
    for(i=1;i<=n;i++)_read(A[i]); 
    for(i=n;i>0;i--) Insert(i);
    TreeDP();
    for(i=0;i=0;i--){
        ans1[i]+=ans1[i+1];
        if(ans1[i+1]) ans2[i]=max(ans2[i],ans2[i+1]); 
    }
    for(i=0;i
        
   
点击复制链接 与好友分享!回本站首页
上一篇:各种排序算法的稳定性和时间复杂度小结
下一篇:机器学习入门之神经网络
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站