初探插头dp

开学那个月学了点新东西，不知道还记不记得了，mark一下

感觉cdq的论文讲的很详细

题主要跟着kuangbin巨做了几道基础的

http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710343.html

还有几道没做，留着坑

感觉广义括号表示法虽然神奇，但一般最小表示法就够用了吧，感觉最小表示法更直观一点

hdu1693

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 typedef long long ll;

 using namespace std;

 ll f[][][<<];

 int a[][];

 int n,m,cas;

 int main()

 {

   scanf("%d",&cas);

   for (int tt=; tt<=cas; tt++)

   {

     scanf("%d%d",&n,&m);

     for (int i=; i<=n; i++)

       for (int j=; j<=m; j++)

         scanf("%d",&a[i][j]);

     printf("Case %d: ",tt);

     memset(f,,sizeof(f));

     f[][m][]=;

     for (int i=; i<=n; i++)

     {

       for (int j=; j<(<<m); j++)

         f[i][][j<<]=f[i-][m][j];

       for (int j=; j<=m; j++)

       {

         for (int st=; st<(<<(m+)); st++)

         {

           int x=<<j,y=<<(j-);

           if (a[i][j])

           {

             if ((st&x)&&(st&y)) f[i][j][st]=f[i][j-][st^x^y];

             else if (!(st&x)&&!(st&y)) f[i][j][st]=f[i][j-][st|x|y];

             else f[i][j][st]=f[i][j-][st]+f[i][j-][st^x^y];

           }

           else {

             if (!(st&x)&&!(st&y)) f[i][j][st]=f[i][j-][st];

             else f[i][j][st]=;

           }

         }

       }

     }

     printf("There are %lld ways to eat the trees.\n",f[n][m][]);

   }

   return ;

 }

hdu1693

poj1793（男人八题!）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 typedef long long ll;

 const int mo=;

 const int maxl=;

 using namespace std;

 struct node{

   int p[mo],nex[maxl],len;

   ll st[maxl],f[maxl];

   void clr()

   {

     len=; memset(p,,sizeof(p));

   }

   void push(ll nw,ll s)

   {

     int x=nw%mo;

     for (int i=p[x];i!=-; i=nex[i])

       if (st[i]==nw)

       {

         f[i]+=s;

         return;

       }

     st[++len]=nw; f[len]=s;

     nex[len]=p[x]; p[x]=len;

   }

 } h[];

 int n,m,cas,p,ex,ey;

 int a[][],b[],v[];

 void get(ll st)

 {

   for (int i=m; i>=; i--)

   {

     b[i]=st&;

     st>>=;

   }

 }

 ll put()

 {

   memset(v,,sizeof(v)); v[]=;

   ll st=; int t=;

   for (int i=; i<=m; i++)

   {

     if (v[b[i]]==-) v[b[i]]=++t;

     b[i]=v[b[i]];

     st<<=; st|=b[i];

   }

   return st;

 }

 void shift()

 {

   for (int i=m;i; i--) b[i]=b[i-];

   b[]=;

 }

 void work(int j,int k)

 {

   if (j==m) shift();

   h[p].push(put(),h[-p].f[k]);

 }

 void dp(int i,int j)

 {

   for (int k=; k<=h[-p].len; k++)

   {

     get(h[-p].st[k]);

     if (!a[i][j])

     {

       b[j]=b[j-]=; work(j,k);

       continue;

     }

     int x=b[j],y=b[j-];

     if (x&&y)

     {

       if ((x==y&&i==ex&&j==ey)||(x!=y))

       {

         b[j]=b[j-]=;

         if (x!=y)

           for (int r=; r<=m; r++) if (b[r]==x) b[r]=y;

         work(j,k);

       }

     }

     else if ((x&&!y)||(!x&&y))

     {

       int r=x+y;

       if (a[i][j+]) {b[j]=r; b[j-]=; work(j,k);}

       if (a[i+][j]) {b[j-]=r; b[j]=; work(j,k);}

     }

     else if (a[i][j+]&&a[i+][j])

     {

       b[j]=b[j-]=m+;

       work(j,k);

     }

   }

 }

 int main()

 {

   char s[];

   scanf("%d%d",&n,&m);

   while (n&&m)

   {

     memset(a,,sizeof(a));

     for (int i=; i<=n; i++)

     {

       scanf("%s",s+);

       for (int j=; j<=m; j++)

         if (s[j]=='.') a[i][j]=;

     }

     for (int i=; i<=m; i++)

     {

       a[n+][i]=;

       a[n+][i]=(i>&&i<m)?:;

     }

     n+=;  ex=n; ey=m;

     h[].clr();

     h[].push(,);  p=;

     for (int i=; i<=n; i++)

       for (int j=; j<=m; j++)

       {

         p^=; h[p].clr();

         dp(i,j);

       }

     ll ans=;

     for (int i=; i<=h[p].len; i++)

       ans+=h[p].f[i];

     printf("%lld\n",ans);

     scanf("%d%d",&n,&m);

   }

   return ;

 }

poj1793

fzu1977

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 typedef long long ll;

 const int mo=;

 const int maxl=;

 using namespace std;

 struct node{

   int p[mo],nex[maxl],len;

   ll st[maxl],f[maxl];

   void clr()

   {

     len=; memset(p,,sizeof(p));

   }

   void push(ll nw,ll s)

   {

     int x=nw%mo;

     for (int i=p[x];i!=-; i=nex[i])

       if (st[i]==nw)

       {

         f[i]+=s;

         return;

       }

     st[++len]=nw; f[len]=s;

     nex[len]=p[x]; p[x]=len;

   }

 } h[];

 int n,m,cas,p,ex,ey;

 int a[][],b[],v[];

 void get(ll st)

 {

   b[m+]=st&; st>>=;

   for (int i=m; i>=; i--)

   {

     b[i]=st&;

     st>>=;

   }

 }

 ll put()

 {

   memset(v,,sizeof(v)); v[]=;

   ll st=; int t=;

   for (int i=; i<=m; i++)

   {

     if (v[b[i]]==-) v[b[i]]=++t;

     b[i]=v[b[i]];

     st<<=; st|=b[i];

   }

   st<<=; st|=b[m+];

   return st;

 }

 void shift()

 {

   for (int i=m;i; i--) b[i]=b[i-];

   b[]=;

 }

 void dp(int i,int j)

 {

   for (int k=; k<=h[p^].len; k++)

   {

     get(h[p^].st[k]);

     if (!a[i][j])

     {

       b[j]=b[j-]=;

       h[p].push(put(),h[p^].f[k]);

       continue;

     }

     int x=b[j],y=b[j-];

     if (b[m+])

     {

       if (!x&&!y&&a[i][j]!=)

       {

         b[j]=b[j-]=;

         h[p].push(put(),h[p^].f[k]);

       }

       continue;

     }

     if (x&&y)

     {

       b[j]=b[j-]=;

       if (x!=y){

         for (int r=; r<=m; r++) if (b[r]==x) b[r]=y;

       }

       else b[m+]=;

       h[p].push(put(),h[p^].f[k]);

     }

     else if ((x&&!y)||(!x&&y))

     {

       int r=x+y;

       if (a[i][j+])

       {

         b[j]=r; b[j-]=;

         h[p].push(put(),h[p^].f[k]);

       }

       if (a[i+][j])

       {

         b[j-]=r; b[j]=;

         h[p].push(put(),h[p^].f[k]);

       }

     }

     else {

       if (a[i][j+]&&a[i+][j])

       {

         b[j]=b[j-]=m+;

         h[p].push(put(),h[p^].f[k]);

       }

       if (a[i][j]==)

       {

         b[j]=b[j-]=;

         h[p].push(put(),h[p^].f[k]);

       }

     }

   }

 }

 int main()

 {

   char s[]; int cas;

   scanf("%d",&cas);

   for (int tt=; tt<=cas; tt++)

   {

     scanf("%d%d",&n,&m);

     memset(a,,sizeof(a));

     for (int i=; i<=n; i++)

     {

       scanf("%s",s+);

       for (int j=; j<=m; j++)

         if (s[j]=='O') a[i][j]=;

         else if (s[j]=='*') a[i][j]=;

     }

     h[].clr();

     h[].push(,);  p=;

     for (int i=; i<=n; i++)

     {

       p^=; h[p].clr();

       for (int k=; k<=h[p^].len; k++)

       {

         get(h[p^].st[k]); shift();

         h[p].push(put(),h[p^].f[k]);

       }

       for (int j=; j<=m; j++)

       {

         p^=; h[p].clr();

         dp(i,j);

       }

     }

     ll ans=;

     for (int i=; i<=h[p].len; i++)

       ans+=h[p].f[i];

     printf("Case %d: %I64d\n",tt,ans);

   }

   return ;

 }

fzu1977

hdu3377

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 typedef long long ll;

 const int mo=;

 const int maxl=;

 const int inf=-;

 using namespace std;

 struct node{

   int p[mo],nex[maxl],len,f[maxl];

   ll st[maxl];

   void clr()

   {

     len=; memset(p,,sizeof(p));

   }

   void push(ll nw,int s)

   {

     int x=nw%mo;

     for (int i=p[x];i!=-; i=nex[i])

       if (st[i]==nw)

       {

         f[i]=max(f[i],s);

         return;

       }

     st[++len]=nw; f[len]=s;

     nex[len]=p[x]; p[x]=len;

   }

 } h[];

 int n,m,cas,p,ex,ey;

 int a[][],b[],v[];

 void get(ll st)

 {

   for (int i=m; i>=; i--)

   {

     b[i]=st&;

     st>>=;

   }

 }

 ll put()

 {

   memset(v,,sizeof(v)); v[]=;

   ll st=; int t=;

   for (int i=; i<=m; i++)

   {

     if (v[b[i]]==-) v[b[i]]=++t;

     b[i]=v[b[i]];

     st<<=; st|=b[i];

   }

   return st;

 }

 void shift()

 {

   for (int i=m;i; i--) b[i]=b[i-];

   b[]=;

 }

 void dp(int i,int j)

 {

   for (int k=; k<=h[-p].len; k++)

   {

     get(h[-p].st[k]);

     int x=b[j],y=b[j-];

     if (i==&&j==)

     {

       if (i<n) {b[j-]=m+; b[j]=; h[p].push(put(),h[-p].f[k]+a[i][j]);}

       if (j<m) {b[j-]=; b[j]=m+; h[p].push(put(),h[-p].f[k]+a[i][j]);}

       continue;

     }

     if (i==n&&j==m)

     {

       if ((!x&&y)||(!y&&x))

       {

         b[j]=b[j-]=;

         h[p].push(put(),h[-p].f[k]+a[i][j]);

       }

       continue;

     }

     if (x&&y)

     {

       if (x!=y)

       {

         b[j]=b[j-]=;

         if (x!=y)

           for (int r=; r<=m; r++) if (b[r]==x) b[r]=y;

         if (j==m) shift();

         h[p].push(put(),h[-p].f[k]+a[i][j]);

       }

     }

     else if ((x&&!y)||(!x&&y))

     {

       int r=x+y;

       if (j<m) {

         b[j]=r; b[j-]=;

         h[p].push(put(),h[-p].f[k]+a[i][j]);

       }

       if (i<n)

       {

         b[j-]=r; b[j]=;

         if (j==m) shift();

         h[p].push(put(),h[-p].f[k]+a[i][j]);

       }

     }

     else {

       if (i<n&&j<m)

       {

         b[j]=b[j-]=m+;

         h[p].push(put(),h[-p].f[k]+a[i][j]);

       }

       b[j]=b[j-]=;

       if (j==m) shift();

       h[p].push(put(),h[-p].f[k]);

     }

   }

 }

 int main()

 {

   int tt=;

   while (scanf("%d%d",&n,&m)!=EOF)

   {

     for (int i=; i<=n; i++)

       for (int j=; j<=m; j++)

         scanf("%d",&a[i][j]);

     if (n==&&m==)

     {

       printf("Case %d: %d\n",++tt,a[][]);

       continue;

     }

     h[].clr();

     h[].push(,);  p=;

     for (int i=; i<=n; i++)

       for (int j=; j<=m; j++)

       {

         p^=; h[p].clr();

         dp(i,j);

       }

     int ans=inf;

     for (int i=; i<=h[p].len; i++)

       ans=max(ans,h[p].f[i]);

     printf("Case %d: %d\n",++tt,ans);

   }

   return ;

 }

hdu3377

poj3133

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 const int maxl=;

 using namespace std;

 struct node{

   int len,f[maxl],st[maxl];

   void clr()

   {

     for (int i=; i<=len; i++) f[st[i]]=-;

     len=;

   }

   void push(int nw,int s)

   {

     if (f[nw]==-)

     {

       st[++len]=nw;

       f[nw]=s;

     }

     else f[nw]=min(f[nw],s);

   }

 } h[];

 int n,m,cas,p;

 int a[][],b[];

 void get(int st)

 {

   for (int i=m; i>=; i--)

   {

     b[i]=st&;

     st>>=;

   }

 }

 int put()

 {

   int st=;

   for (int i=; i<=m; i++) {st<<=; st|=b[i];}

   return st;

 }

 void shift()

 {

   for (int i=m;i; i--) b[i]=b[i-];

   b[]=;

 }

 void dp(int i,int j)

 {

   for (int k=; k<=h[-p].len; k++)

   {

     get(h[-p].st[k]);

     int x=b[j],y=b[j-],st=h[-p].st[k];

     if (a[i][j]!=)

     {

       if (!a[i][j]&&!x&&!y) h[p].push(st,h[-p].f[st]);

       else if (a[i][j]>)

       {

         if (((x&&!y)||(!x&&y))&&(x+y==a[i][j])) {b[j]=b[j-]=; h[p].push(put(),h[-p].f[st]+);}

         else if (!x&&!y)

         {

           if (a[i][j+]==a[i][j]||a[i][j+]==) {b[j]=a[i][j]; b[j-]=; h[p].push(put(),h[-p].f[st]+);}

           if (a[i+][j]==a[i][j]||a[i+][j]==) {b[j-]=a[i][j]; b[j]=; h[p].push(put(),h[-p].f[st]+);}

         }

       }

       continue;

     }

     if (x&&y&&x==y) {b[j]=b[j-]=; h[p].push(put(),h[-p].f[st]+);}

     else if ((x&&!y)||(!x&&y))

     {

       int r=x+y;

       if (a[i][j+]==||a[i][j+]==r) {b[j]=r; b[j-]=; h[p].push(put(),h[-p].f[st]+);}

       if (a[i+][j]==||a[i+][j]==r) {b[j-]=r; b[j]=; h[p].push(put(),h[-p].f[st]+);}

     }

     else if (!x&&!y)

     {

       if (a[i][j+]&&a[i+][j])

       {

         if (a[i][j+]==&&a[i+][j]==)

         {

           b[j]=b[j-]=;  h[p].push(put(),h[-p].f[st]+);

           b[j]=b[j-]=;  h[p].push(put(),h[-p].f[st]+);

         }

         else if (a[i][j+]==&&a[i+][j]==||a[i][j+]==&&a[i+][j]==||a[i+][j]==&&a[i][j+]==) {b[j]=b[j-]=; h[p].push(put(),h[-p].f[st]+);}

         else if (a[i][j+]==&&a[i+][j]==||a[i][j+]==&&a[i+][j]==||a[i+][j]==&&a[i][j+]==) {b[j]=b[j-]=; h[p].push(put(),h[-p].f[st]+);}

       }

       h[p].push(st,h[-p].f[st]);

     }

   }

 }

 int main()

 {

   h[].len=h[].len=;

   memset(h[].f,,sizeof(h[].f));

   memset(h[].f,,sizeof(h[].f));

   scanf("%d%d",&n,&m);

   while (n&&m)

   {

     memset(a,,sizeof(a));

     for (int i=; i<=n; i++)

     {

       for (int j=; j<=m; j++)

       {

         scanf("%d",&a[i][j]);

         if (a[i][j]==||a[i][j]==) a[i][j]^=;

       }

     }

     h[].push(,);  p=;

     for (int i=; i<=n; i++)

     {

       p^=;  h[p].clr();

       for (int k=; k<=h[-p].len; k++)

       {

         get(h[-p].st[k]); int st=h[-p].st[k]; shift();

         h[p].push(put(),h[-p].f[st]);

       }

       for (int j=; j<=m; j++)

       {

         p^=; h[p].clr();

         dp(i,j);

       }

     }

     int ans=;

     for (int i=; i<=h[p].len; i++)

     {

       int st=h[p].st[i];

       ans+=h[p].f[st];

     }

     if (ans>) ans-=;

     printf("%d\n",ans);

     h[].clr(); h[].clr();

     scanf("%d%d",&n,&m);

   }

   return ;

 }

poj3133

hdu4285

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 typedef long long ll;

 const int ha=;

 const int maxl=;

 const int mo=;

 using namespace std;

 struct node{

   int p[ha],nex[maxl],len,f[maxl];

   ll st[maxl];

   void clr()

   {

     len=; memset(p,,sizeof(p));

   }

   void push(ll nw,int s)

   {

     int x=nw%ha;

     for (int i=p[x];i!=-; i=nex[i])

       if (st[i]==nw)

       {

         f[i]=(f[i]+s)%mo;

         return;

       }

     st[++len]=nw; f[len]=s;

     nex[len]=p[x]; p[x]=len;

   }

 } h[];

 int n,m,cas,p,t;

 int a[][],b[],v[];

 void get(ll st)

 {

   b[m+]=st&; st>>=;

   for (int i=m; i>=; i--)

   {

     b[i]=st&;

     st>>=;

   }

 }

 ll put()

 {

   memset(v,,sizeof(v)); v[]=;

   ll st=; int t=;

   for (int i=; i<=m; i++)

   {

     if (v[b[i]]==-) v[b[i]]=++t;

     b[i]=v[b[i]];

     st<<=; st|=b[i];

   }

   st<<=; st|=b[m+];

   return st;

 }

 void shift()

 {

   for (int i=m;i; i--) b[i]=b[i-];

   b[]=;

 }

 bool check(int j)

 {

   bool ff=;

   for (int i=; i<j-; i++)

     if (b[i]) ff^=;

   if (!ff) return ;

   for (int i=j+; i<=m; i++)

     if (b[i]) ff^=;

   return ff;

 }

 void dp(int i,int j)

 {

   for (int k=; k<=h[p^].len; k++)

   {

     get(h[p^].st[k]);

     if (!a[i][j])

     {

       b[j]=b[j-]=;

       h[p].push(put(),h[p^].f[k]);

       continue;

     }

     int x=b[j],y=b[j-];

     if (b[m+]==t) continue;

     if (x&&y)

     {

       b[j]=b[j-]=;

       if (x!=y){

         for (int r=; r<=m; r++) if (b[r]==x) b[r]=y;

       }

       else {

         if (check(j)) ++b[m+]; else continue;

       }

       h[p].push(put(),h[p^].f[k]);

     }

     else if ((x&&!y)||(!x&&y))

     {

       int r=x+y;

       if (a[i][j+])

       {

         b[j]=r; b[j-]=;

         h[p].push(put(),h[p^].f[k]);

       }

       if (a[i+][j])

       {

         b[j-]=r; b[j]=;

         h[p].push(put(),h[p^].f[k]);

       }

     }

     else {

       if (a[i][j+]&&a[i+][j])

       {

         b[j]=b[j-]=m+;

         h[p].push(put(),h[p^].f[k]);

       }

     }

   }

 }

 int main()

 {

   char s[]; int cas;

   scanf("%d",&cas);

   while (cas--)

   {

     scanf("%d%d%d",&n,&m,&t);

     memset(a,,sizeof(a));

     for (int i=; i<=n; i++)

     {

       scanf("%s",s+);

       for (int j=; j<=m; j++)

         if (s[j]=='.') a[i][j]=;

     }

     h[].clr();

     h[].push(,);  p=;

     for (int i=; i<=n; i++)

     {

       p^=; h[p].clr();

       for (int k=; k<=h[p^].len; k++)

       {

         get(h[p^].st[k]); shift();

         h[p].push(put(),h[p^].f[k]);

       }

       for (int j=; j<=m; j++)

       {

         p^=; h[p].clr();

         dp(i,j);

       }

     }

     int ans=;

     for (int i=; i<=h[p].len; i++)

     {

       get(h[p].st[i]);

       if (b[m+]==t) ans=(ans+h[p].f[i])%mo;

     }

     printf("%d\n",ans);

   }

   return ;

 }

hdu4285

矩阵乘法加速插头dp的几题一直想做，抽时间要补一下