Tag : DP « Lavender's Blog

about 4 years ago

【bzoj2423】最长公共子序列

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define maxn 5001

#define Mod 100000000

using namespace std;
int dp[2][maxn]={0},sum[2][maxn]={0}; 
char a[maxn],b[maxn];
int n,m;
void add(int &x,int y)
{
    x=(x+y)%Mod;
}
void dec(int &x,int y)
{
    x=(x-y+Mod)%Mod;
}
int main()
{    
    scanf("%s%s",a+1,b+1);
    int i,j,now;
    n=strlen(a+1)-1;m=strlen(b+1)-1;
    for (i=0;i<=m;i++) sum[0][i]=1;
    for (i=1;i<=n;i++)
    {now=i&1;
    memset(dp[now],0,sizeof(dp[now]));
    memset(sum[now],0,sizeof(sum[now]));
    sum[now][0]=1;
    for (j=1;j<=m;j++)
    {    //一开始自己yy的。注意最后一步减去是重点。
        if (a[i]==b[j]) dp[now][j]=dp[now^1][j-1]+1;
        dp[now][j]=max(dp[now^1][j],max(dp[now][j-1],dp[now][j]));
        if (a[i]==b[j]&&dp[now][j]==dp[now^1][j-1]+1) add(sum[now][j],sum[now^1][j-1]);
        if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
        if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);
        if (dp[now][j]==dp[now][j-1]&&dp[now^1][j-1]==dp[now^1][j]&&dp[now^1][j]==dp[now][j-1])dec(sum[now][j],sum[now^1][j-1]);
        //如果a[i]!=b[j]，dp[now][j-1]==dp[now^1][j],则说明他们==dp[now^1][j-1]
        //   这样的话就会多算一遍，必须减去【MARK!!】 
    /* WYL版。简单直白。 
        if (a[i]==b[j]) 
        {dp[now][j]=dp[now^1][j-1]+1;
        dp[now][j]=max(dp[now^1][j],max(dp[now][j-1],dp[now][j]));
        if (dp[now][j]==dp[now^1][j-1]+1) add(sum[now][j],sum[now^1][j-1]);
        if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
        if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);}
        else
        {
            dp[now][j]=max(dp[now^1][j],dp[now][j-1]);
            if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
            if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);           
            if (dp[now^1][j]==dp[now][j-1]&&dp[now^1][j-1]==dp[now][j-1])
            //if (dp[now][j]==dp[now^1][j-1])也是满足的，因为不可能dp[now][j-1],dp[now^1][j]<dp[now^1][j-1] 
             dec(sum[now][j],sum[now^1][j-1]);
        }*/
    }}
    printf("%d\n%d\n",dp[n&1][m],sum[n&1][m]);
}

June 25, 2014 09:45
Permalink
Comments

almost 4 years ago

学了好久调了好久……
仙人掌dp分成在环上和树上就好
但是有很多的细节要注意
论静态查错是多么的重要
代码还有一点小问题，sth大爷的数据没有全过。poj的还没试过
-------------------------update--------------------------------
fe是为了判断二元环而设的，但是此题二元环可直接当树边处理，没有影响。用fa判断即可
而且用fe会在sth的数据上wa3个点
但是sth用feA了自己的数据……
但是他的边从1开始……0.0不知道怎么异或找的相反边……
仙人掌最多有多少条边的计算一开始也不知道……poj mle。。
初步计算应该是最坏情况下是二元环，这样就是n*2条边，加上反向边4*n
代码中用fe的地方注释掉了换成了fa

于是冲到了pojrank1……

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define maxn 50001

#define maxm 200001

using namespace std;
int next[maxm],point[maxn],v[maxm];
int dfn[maxn],low[maxn],fe[maxn],f[maxn],fa[maxn];
int n,m,widen=-1,ans=0,tot=0;
int loop[maxn*2],ln=0,start,til;
struct node
{int num,pos;} q[maxn*2];
inline int readln()
{
    char c=getchar();int result=0,bj=1;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
inline void addedge(int x,int y)
{
    widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
    widen++;next[widen]=point[y];point[y]=widen;v[widen]=x;
}
void workonloop()
{
    int i,x;
    memcpy(loop+ln+1,loop+1,sizeof(int)*ln);
    q[1].pos=1;q[1].num=f[loop[1]]-1;
    start=1;til=1;
    for (i=2;i<=ln*2;i++)//注意下面所有都是环上的！！！ 
    {
        for (;q[start].pos<i-(ln)/2;start++);
        ans=max(ans,q[start].num+f[loop[i]]+i);
        x=f[loop[i]]-i;
        for (;start<=til&&q[til].num<=x;til--);//会出现start>til的情况！！ 
        q[++til].num=x;q[til].pos=i; 
    }
}
void dfs(int x)
{
    dfn[x]=low[x]=++tot;
    for (int k=point[x];k!=-1;k=next[k])
    if (fa[x]!=v[k])
//  if ((k^1)!=fe[x])                                                                                                                                                                                                                                         
    {
    if (dfn[v[k]])
        low[x]=min(low[x],dfn[v[k]]);
    else 
    {
        fe[v[k]]=k;fa[v[k]]=x;dfs(v[k]);
        low[x]=min(low[x],low[v[k]]);
    }
    }
    for (int k=point[x];k!=-1;k=next[k])
    if (fa[x]!=v[k])
//  if ((k^1)!=fe[x])
    {
        if (low[v[k]]>dfn[x])//在以x为根的子树里 
        {
            ans=max(ans,f[x]+1+f[v[k]]);
            f[x]=max(f[x],f[v[k]]+1);
        }
        else
        if (fa[v[k]]!=x&&dfn[x]<dfn[v[k]])
        //if (fe[v[k]]!=k&&dfn[x]<dfn[v[k]])//非树边且x点是靠上的点 
        {
            ln=0;int now=v[k];
            for (;x!=now;now=fa[now])
                loop[++ln]=now;
            loop[++ln]=x;
            workonloop();
            for (int i=1;i<ln;i++)
                f[x]=max(f[x],f[loop[i]]+min(i,ln-i));
        }
    }
}
int main()
{
    int i,j,k,x,y;
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    n=readln();m=readln();
    for (i=1;i<=m;i++)
    {
        k=readln();x=readln();
        for (j=1;j<k;j++,x=y)
        {
            y=readln();
            addedge(x,y);
        }
    }
    dfs(1);
    printf("%d\n",ans);
}

DP
仙人掌

September 03, 2014 20:50
Permalink
Comments

almost 4 years ago

【bzoj3203】【凸包】【三分】【dp】保护出题人

题目很恶心……

注意僵尸是可以复活的。新加的僵尸排在最前面

但是做的时候依旧是从后面添僵尸

【具体看gty的题解……】

很明显可以维护一个凸壳。点坐标为（i*d,sum[i]）

查询的时候只需要找（xi+i*d,sum[i]）与点j斜率最大的即可

下凸壳

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define kk I64d
#define maxn 100001
#define eps 1e-6
using namespace std;
long double result=0.0;
int stack[maxn];
long long d;int n,top=0;
long long a[maxn]={0},sum[maxn]={0},x[maxn]={0};
long long readln()
{
    char c=getchar();long long result=0;int  bj=1;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
double fabs(double a)
{
    if (a>0) return a; else return -a;
}
int dcmp(double a,double b)
{
    if (fabs(a-b)<eps) return 0;
    if (a>b) return 1;else return -1;
}
double xl(int a,int b)
{
    return (sum[a]-sum[b-1])/(x[a]+d*a-d*b);
}
double xltb(int a,int b)
{
    return (sum[a-1]-sum[b-1])/(d*a-d*b);
}
int find(int left,int right,int k)
{
    int lmid,rmid;
    while (left+1<right)
    {
        lmid=left+(right-left+1)/3;rmid=left+(right-left+1)*2/3;
        if (dcmp(xl(k,lmid),xl(k,rmid))>0) right=rmid-1;
        else left=lmid+1;
    }
    if (dcmp(xl(k,left),xl(k,right))>0) return left;
    else return right;
}
int main()
{
    int i,k;
    n=readln();d=readln();
    for (i=1;i<=n;i++)
    {
        a[i]=readln();x[i]=readln();sum[i]=sum[i-1]+a[i];
    }
    for (i=1;i<=n;i++)
      {
        while (top>=2&&dcmp(xl(i,stack[top-1]),xl(i,stack[top]))<0) top--;
        stack[++top]=i;
        k=find(1,top,i);
        result+=(sum[i]-sum[k-1])/(long double)(x[i]+d*i-d*k);
      }
    printf("%d\n",(int)(result+0.5));
}

September 29, 2014 13:52
Permalink
Comments

almost 4 years ago

【bzoj2553】【ac自动机】【dp】【矩阵优化】禁忌

ac自动机多和dp联系在一起
http://hi.baidu.com/wwwaaannngggrs/item/b2b67acccea55f0dc710b211
f数组是邻接矩阵，自乘k次代表沿矩阵走k步，f[i][j]表示i到j的方案数
f[i][j] 是j转移到i的可能性
ans数组是结果。由于在数组里的下标都往后移了一位,ans[1][1]=f[0][0]=1【1、第0位匹配根节点的概率是100%。2、若为0的话会导致答案乘0失解】
f*ans的答案ans'[i][j] 代表n个点下一步转移到i点的可能性【注意矩阵乘法不满足交换律！！！！注意查错！被坑了好久……】
代码里有重载。
orz gty

/**************************************************************
    Problem: 2553
    User: LaVenDer
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:1376 kb
****************************************************************/

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
struct matrix
{
    long double a[80][80];
    int sx,sy;
    void dowith(int x,int y)
    {
        sx=x;sy=y;memset(a,0,sizeof(a));
    }
} ans,f;
matrix operator*(const matrix a,const matrix b)
{
    matrix temp;temp.dowith(a.sx,b.sy);
    for (int i=1;i<=temp.sx;i++)
      for (int j=1;j<=temp.sy;j++)
      {
        for (int k=1;k<=a.sy;k++)
          temp.a[i][j]+=a.a[i][k]*b.a[k][j];
      }
    return temp;
}
struct ac
{
    int ch[101][27];
    int fail[101],last[101],val[101];
    int sz,size;
    void dowith(int k)
    {
        sz=0;size=k;
        memset(fail,0,sizeof(fail));
        memset(last,0,sizeof(last));
        memset(val,0,sizeof(val));
        memset(ch,0,sizeof(ch));
    }
    void insert(char *st,int color)
    {
        int l=strlen(st),i;
        int pos=0;
        for (i=0;i<l;i++)
          st[i]=st[i]-'a'+1;
        for (i=0;i<l;i++)
          {
            if (!ch[pos][st[i]]) {ch[pos][st[i]]=++sz;}
            pos=ch[pos][st[i]];
          }
        val[pos]=color;
    }
    queue<int>q;
    void prepare()
    {
        int i,j,a,k,pos=0;
        for (i=1;i<=size;i++)
          if (ch[pos][i]) q.push(ch[pos][i]);
        while (!q.empty())
        {
            pos=q.front();q.pop();
            for (i=1;i<=size;i++)
            {
                if (!ch[pos][i]){ch[pos][i]=ch[fail[pos]][i];continue;}
                q.push(ch[pos][i]);
                j=fail[pos];
                while (j&&!ch[j][i]) j=fail[j];
                j=ch[j][i];
                fail[ch[pos][i]]=j;
            }
        }
    }
} t;
int n,len,alphabet;
char st[20];
matrix ksm(matrix f,int x)
{
    matrix temp;temp.dowith(f.sx,f.sy);
    for (int i=1;i<=f.sx;i++)
      temp.a[i][i]=1;
    for (int i=x;i>0;i>>=1)
    {
        if (i&1) temp=temp*f;
        f=f*f;
    }
    return temp;
}
int main()
{
    int i,j,k;
    scanf("%d%d%d",&n,&len,&alphabet);
    t.dowith(alphabet);
    for (i=1;i<=n;i++)
     {
        scanf("%s",st);
        t.insert(st,i);
     }
    t.prepare();
    f.dowith(t.sz+2,t.sz+2);
    long double temp=1.0/(long double)alphabet;
    for (i=0;i<=t.sz;i++)
    {
        for (j=1;j<=alphabet;j++)
          if (t.val[i]==0)
          {
            if (t.val[t.ch[i][j]])
            {
                f.a[1][i+1]+=temp;
                f.a[t.sz+2][i+1]+=temp;
            }
            else
              f.a[t.ch[i][j]+1][i+1]+=temp;
          }
    }
    f.a[t.sz+2][t.sz+2]=1;
    f=ksm(f,len); 
    ans.dowith(t.sz+2,1);
    ans.a[1][1]=1;
    ans=f*ans;
    printf("%.12lf\n",(double)ans.a[t.sz+2][1]);
}

September 29, 2014 14:23
Permalink
Comments

almost 4 years ago

【bzoj1010】【dp】【斜率优化】玩具装箱

终于对斜率优化有了一点理解……

calc(x,y)<g[t] 则x比y要优。calc（x，y）的值其实就是斜率

在入队的时候，设i<j<k,若calc(k,j)<calc（j,i）【斜率的比较。即维护凸壳】则无论calc是否大于g[t],j都不会是最优决策弹出

出队时只需要找到calc(x,y)<g[t]中最优的x即可

坑啊……注意int*int=long long 的话会爆==开心的栽在了这里半个小时……

/**************************************************************
    Problem: 1010
    User: Lavender6895
    Language: C++
    Result: Accepted
    Time:136 ms
    Memory:2368 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 50001
using namespace std;
int q[maxn+5]={0},c[maxn]={0};
long long f[maxn]={0},g[maxn]={0},sum[maxn]={0};
int n,l;
double calc(int x,int y)
{
    return ((double)f[x]-f[y]+g[x]*g[x]-g[y]*g[y])/(2*g[x]-2*g[y]);
}
int readln()
{
    char c;int result=0,bj=1;
    while (c!='-'&&(!(c<='9'&&c>='0'))) c=getchar();
    if (c=='-') {bj=-1;c=getchar();}
    while (c<='9'&&c>='0') {result=result*10+c-'0';c=getchar();}
    return result*bj;
}
int main()
{
n=readln();l=readln();
    long long s=0;int i,start,til,k;
    for (i=1;i<=n;i++) c[i]=readln(),s+=c[i],g[i]=s+i;
    start=1;til=1;q[start]=0;
    for (i=2;i<=n;i++)
      {
        while (start<til&&calc(q[start+1],q[start])<g[i]-l-1) start++;
        k=q[start];
        f[i]=f[k]+(g[i]-g[k]-(l+1))*(g[i]-g[k]-(l+1));
        while (start<til&&calc(i,q[til])<calc(q[til],q[til-1])) til--;
        q[++til]=i;
      }
    printf("%lld\n",f[n]);
}

September 29, 2014 14:25
Permalink
Comments

over 3 years ago

【bzoj1294】【状压dp】围豆豆

终于发现了自己的手残
因为范围不大所以用搜索来转移状态。
转移的时候用了射线法

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
struct node{int x,y,num;};
queue<node> q;
int f[12][12][1<<11],n,m,d,ans=0,a[12],v[1<<11],pos[12][2];
char map[12][12];
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
int calc(int num,int x,int y,int xx)
{
    for (int i=1;i<=d;i++)
        if (pos[i][1]>y&&(x==pos[i][0]&&xx>pos[i][0]||xx==pos[i][0]&&x>pos[i][0]))   num=num^(1<<i-1);
    return num;
}
int get(int st,int x,int y,int xx)
{
    for(int i=1;i<=d;i++)
        if(y<pos[i][1]&&(x==pos[i][0]&&xx>pos[i][0]||x>pos[i][0]&&xx==pos[i][0]))
            st^=1<<i-1;
    return st;
}
void search(int x,int y)
{
    int i,xx,yy,num;
    memset(f,-1,sizeof(f));
    q.push((node){x,y,0} );f[x][y][0]=0; 
    while (!q.empty())
    {
        node temp=q.front();q.pop();
        for (i=0;i<4;i++)
        {
            xx=temp.x+dx[i];yy=temp.y+dy[i];
            if (xx<=n&&xx>=1&&yy<=m&&yy>=1&&map[xx][yy]=='0')
            {
                num=get(temp.num,temp.x,temp.y,xx);
                if (f[xx][yy][num]==-1)
                {
                    f[xx][yy][num]=f[temp.x][temp.y][temp.num]+1;
                    q.push((node){xx,yy,num});
                }
            } 
        }
    }
    for (i=1;i<(1<<d);i++)   if (f[x][y][i]!=-1) ans=max(ans,v[i]-f[x][y][i]);
}
int main()
{
    int i,j,posn=0,k;
    scanf("%d%d%d",&n,&m,&d);
    for (i=1;i<=d;i++) scanf("%d",&a[i]);
    for (i=1;i<(1<<d);i++)   for (j=i,k=1;k<=d;k++)   if (j&(1<<k-1))    v[i]+=a[k];
    for (i=1;i<=n;i++)
        {
            scanf("%s",map[i]+1);
            for (j=1;j<=m;j++)
                if (map[i][j]!='0'&&map[i][j]!='#')   pos[map[i][j]-'0'][0]=i,pos[map[i][j]-'0'][1]=j;
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)   if(map[i][j]=='0')    search(i,j);
    printf("%d\n",ans);
}

bzoj
DP

October 25, 2014 08:21
Permalink
Comments

【bzoj2423】最长公共子序列

【bzoj1023】【仙人掌dp】cactus仙人掌图

于是冲到了pojrank1……

【bzoj3203】【凸包】【三分】【dp】保护出题人

【bzoj2553】【ac自动机】【dp】【矩阵优化】禁忌

【bzoj1010】【dp】【斜率优化】玩具装箱

【bzoj1294】【状压dp】围豆豆