注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

插头DP  

2015-03-11 15:19:05|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1519. Formula 1

Time limit: 1.0 second

Problem illustration

Input

The first line contains the integer numbers N and M (2 ≤ NM ≤ 12).

Output

You should output the desired number of ways. It is guaranteed, that it does not exceed 263-1.

Samples

inputoutput
4 4
**..
....
....
....
2
4 4
....
....
....
....
6
#include<cstdio>
#include<cstring>
#define ct continue
#define H 1999997
#define N 600010
using namespace std;
typedef long long ll;
int t,n,k,nn,mm,o,w,r,zhan,pre,now,m,i,j,q,p;
int st[2][N],has[H],tot[2],E[15],b[15][15];
ll f[2][N],ans,s;
char a[15];

inline void hash(int a,ll b){
     int j=a%H;
     while (has[j]){
     if (a==st[t][has[j]]){
        f[t][has[j]]+=b;return;
        }
     j++;
     if (j>=H)j=0;
     }
     tot[t]++;
     has[j]=tot[t];
     st[t][has[j]]=a;f[t][has[j]]=b;
}

int main()
{
 scanf("%d%d",&n,&m);
 for (i=1;i<=12;i++)E[i]=i*2;
 for (i=1;i<=n;i++){
   scanf("%s",a+1);
   for (j=1;j<=m;j++)if (a[j]=='*')b[i][j]=0;
                     else b[i][j]=1,nn=i,mm=j;  
       }
 t=1;
 f[t][1]=1;tot[1]=1;
 for (i=1;i<=n;i++){
  for (j=1;j<=m;j++){
  t^=1;tot[t]=0;
  memset(has,0,sizeof(has));
  for (o=1;o<=tot[t^1];o++){
      pre=st[t^1][o];s=f[t^1][o];
      q=(pre>>E[j-1])&3;
      p=(pre>>E[j])&3;
  if (!b[i][j]){
       if ((!q)&&(!p))hash(pre,s);
          }else {
                
  if ((!q)&&(!p)){
     if (b[i+1][j]&&b[i][j+1]){
          now=pre+1*(1<<(E[j-1]))+2*(1<<(E[j]));
          hash(now,s);
     }ct;      
                }//##
                
  if (!q)    {
     if (b[i][j+1])hash(pre,s);
     if (b[i+1][j]){
        now=pre-p*(1<<(E[j]))+p*(1<<(E[j-1]));
        hash(now,s);
                    }
             ct;
             }//#),#(
  if (!p)    {
     if (b[i+1][j])hash(pre,s);
     if (b[i][j+1]){
        now=pre-q*(1<<(E[j-1]))+q*(1<<E[j]);
        hash(now,s);
                    }
     ct;
             }//)#,(#
  if (q==1)  {
   if (p==2){
      if (i==nn&&j==mm)ans+=s;
             }//最后合并回路 
      else {
           for (r=j,zhan=0;r<=n;r++){
               w=(pre>>(2*r))&3;
               if (w==1)zhan++;else 
               if (w==2)zhan--;
               if (!zhan)break;
               }
           now=pre-1*(1<<(E[j-1]))-1*(1<<E[j]);
           now-=1*(1<<(2*r));
           hash(now,s);
           }//((
             }else 
             {
  if (p==2){
            for (r=j-1,zhan=0;r>=1;r--){
               w=(pre>>(2*r))&3;
               if (w==1)zhan++;else 
               if (w==2)zhan--;
               if (!zhan)break;
               }
           now=pre-2*(1<<(2*(j-1)))-2*(1<<(2*j));
           now+=1*(1ll<<(2*r));
            hash(now,s);
            }else//))
            {
  now=pre-2*(1<<(2*(j-1)))-1*(1<<(2*j));
  hash(now,s);
            }
             }  
  }//空格子
  }
  }
  for (r=1;r<=tot[t];r++)st[t][r]=(st[t][r]<<2);
  }
 printf("%I64d\n",ans);
 return 0;
}

逐格转移,明白插头轮廓线概念。
  评论这张
 
阅读(126)| 评论(3)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018