模板—插头dp（Ural 1519 Formula 1）

括号表示法：

据说比下一个要快而且灵活。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define LL long long

 #define MAXN 20000

 #define HASH 23333

 #define ma(x,y) memset(x,y,sizeof(x))

 using namespace std;

 struct Hash_map

 {

     int size,first[HASH],next[MAXN];

     #define f(x) first[x]

     #define n(x) next[x]

     LL sta[MAXN],sum[MAXN];

     void init(){size=;ma(first,-);ma(sum,);}

     void push(LL states,LL Sum)

     {

         int pos=(states%HASH+HASH)%HASH;

         for(int i=f(pos);i>=;i=n(i))

             if(sta[i]==states){sum[i]+=Sum;return;}

         sta[size]=states;

         sum[size]=Sum;

         n(size)=f(pos);f(pos)=size++;

     }

 }dp[];

 int n,m,map[][],bin[],fx,fy;//最后一个可行点坐标

 int now,pre;

 int mov[]={,,,,,,,,,,,,};

 inline int getbit(LL st,int k){return (st>>mov[k])&;}//第k位状态

 inline int pybit(LL st,int k){return st<<mov[k];}//平移k位

 inline LL clrbit(LL st,int i,int j){return st&(~(<<mov[i]))&(~(<<mov[j]));}//清空i，j位

 inline int fl(LL st,int pos)//从左往右找和当前pos位置匹配的右括号

 {

     int cnt=;

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

     {

         int k=getbit(st,i);

         if(k==)cnt++;

         else if(k==)cnt--;

         if(!cnt)return i;

     }

 }

 inline int fr(LL st,int pos)//从右往左找和当前pos位置匹配的左括号

 {

     int cnt=;

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

     {

         int k=getbit(st,i);

         if(k==)cnt--;

         else if(k==)cnt++;

         if(!cnt)return i;

     }

 }

 void DP(int x,int y,int k)

 {

     int l=getbit(dp[pre].sta[k],y-);

     int up=getbit(dp[pre].sta[k],y);

     LL st=clrbit(dp[pre].sta[k],y-,y);

     LL v=dp[pre].sum[k];

     if(!l&&!up)

     {

         if(!map[x][y]){dp[now].push(st,v);return;}

         if(x<n&&y<m&&map[x+][y]&&map[x][y+])

             dp[now].push(st|pybit(,y-)|pybit(,y),v);

     }

     else if(!l||!up)

     {

         int e=l+up;

         if(x<n&&map[x+][y])

             dp[now].push(st|pybit(e,y-),v);

         if(y<m&&map[x][y+])

             dp[now].push(st|pybit(e,y),v);

     }

     else if(l==&&up==)

         dp[now].push(st^pybit(,fl(st,y)),v);

     else if(l==&&up==)

         dp[now].push(st^pybit(,fr(st,y-)),v);

     else if(l==&&up==)

         dp[now].push(st,v);

     else if(x==fx&&y==fy)

         dp[now].push(st,v);

 }

 LL solve()

 {

     dp[].init();

     dp[].push(,);

     now=,pre=;

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

     {

         pre=now,now^=;dp[now].init();

         for(int k=;k<dp[pre].size;k++)

             dp[now].push(pybit(dp[pre].sta[k],),dp[pre].sum[k]);

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

         {

             pre=now,now^=;dp[now].init();

             for(int k=;k<dp[pre].size;k++)

                 DP(i,j,k);

         }

     }

     for(int i=;i<dp[now].size;i++)

         if(dp[now].sta[i]==)

             return dp[now].sum[i];

     return ;

 }

 signed main()

 {

 //    freopen("in.txt","r",stdin);                                    

     bin[]=;for(int i=;i<=;i++)bin[i]=bin[i-]*;

     cin>>n>>m;char t;

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

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

         {

             cin>>t;

             if(t=='*')map[i][j]=;

             else map[i][j]=;

         }

     fx=;

     for(int i=n;i>&&!fx;i--)

         for(int j=m;j>&&!fx;j--)

         if(map[i][j])

             fx=i,fy=j;

     if(fx==)puts("");

     else cout<<solve()<<endl;

 }

括号表示法（这个是自己写的）

最小表示法（看不懂，下面是标程）：

不过连我都能看出来它慢那它就是真的慢了。而且我也并没有觉得它好理解……

找到一个和自己码风相似的不容易啊……

 #include<bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int maxn=,inc=,bit=;//3位二进制以及111的表示

 int n,m,now,pre,code[],bin[],res[];//用来表示状态的每一位的数值

 char gp[][],fx,fy;//图和最后的可行点

 struct node//离散化hash

 {

     int head[maxn],next[maxn],size;

     LL sum[maxn],sta[maxn];

     void clear()

     {

         memset(head,-,sizeof(head));

         size=;

     }

     void push(LL st,const LL v)

     {

         LL hash=st%maxn;

         for(int i=head[hash];i>=;i=next[i])

         {

             if(sta[i]==st)

             {

                 sum[i]+=v;

                 return ;

             }

         }

         sta[size]=st,sum[size]=v;

         next[size]=head[hash],head[hash]=size++;

     }

 }dp[];

 inline LL encode(int m)//将code转换成状态

 {

     LL st=;

     int cnt=;

     memset(bin,-,sizeof(bin));

     bin[]=;

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

     {

         if(bin[code[i]]==-)

             bin[code[i]]=cnt++;

         code[i]=bin[code[i]];

         st<<=inc;

         st|=code[i];

     }

     return st;

 }

 inline void decode(LL st,int m)//将状态转换成code

 {

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

     {

         code[i]=st&bit;

         st>>=inc;

     }

 }

 void DP(int x,int y,int k)//dp具体情况具体分析

 {

     decode(dp[pre].sta[k],m);

     int l=code[y-];

     int up=code[y];

     code[y-]=code[y]=;

     memcpy(res,code,sizeof(code));

     LL v=dp[pre].sum[k];

     if(!l&&!up)

     {

         if(gp[x][y]=='*')

             dp[now].push(encode(m),v);

         else if(x<n&&y<m&&gp[x+][y]=='.'&&gp[x][y+]=='.')

         {

             code[y]=code[y-]=bit;

             dp[now].push(encode(m),v);

         }

     }

     else if(!l||!up)

     {

         int e=l+up;

         if(x<n&&gp[x+][y]=='.')

         {

             code[y-]=e;

             dp[now].push(encode(m),v);

             memcpy(code,res,sizeof(res));

         }

         if(y<m&&gp[x][y+]=='.')

         {

             code[y]=e;

             dp[now].push(encode(m),v);

         }

     }

     else if(l!=up)

     {

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

             if(code[i]==up)

                 code[i]=l;

         dp[now].push(encode(m),v);

     }

     else if(x==fx&&y==fy)

         dp[now].push(encode(m),v);

 }

 LL solve()

 {

     dp[].clear();//初始化状态

     dp[].push(,);

     now=,pre=;

     for(int i=;i<=n;i++)//逐格逐状态枚举转移

     {

         pre=now,now^=,dp[now].clear();

         for(int k=;k<dp[pre].size;k++)//轮廓线行转移

             dp[now].push(dp[pre].sta[k]<<inc,dp[pre].sum[k]);

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

         {

             pre=now,now^=,dp[now].clear();

             for(int k=;k<dp[pre].size;k++)

             {

                 DP(i,j,k);

             }

         }

     }

     for(int i=;i<dp[now].size;i++)

         if(dp[now].sta[i]==)

             return dp[now].sum[i];

     return ;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         for(int i=;i<=n;i++)//都是从1开始

             scanf("%s",&gp[i][]);

         fx=fy=;

         for(int i=n;i>&&!fx;i--)//寻找最终的位置

             for(int j=m;j>&!fx;j--)

                 if(gp[i][j]=='.')

                     fx=i,fy=j;

         if(fx==)puts("");

         else cout<<solve()<<endl;

     }

 }

最小表示法（摘自某大佬）

巴特西

模板—插头dp（Ural 1519 Formula 1）

最新文章

热门文章