首页 > 代码库 > 【Ural】1519 Formula 1

【Ural】1519 Formula 1

2024-09-13 15:18:15   215人阅读

【算法】插头DP

【题解】

【算法】动态规划

基于连通性状态压缩的动态规划问题 论文题

http://www.cnblogs.com/kuangbin/ 题解+代码

1.注意换行处理

2.在最后一格时向右向下都没有路，而向右和向下的状态是需要判定有没有路的，所以可以保证最后一格的队列中的状态只有回路，即答案。

状态转移之前判断是否无障碍(转移条件)十分重要，也是哈希队列优化的精髓所在!

过程：

状态(k进制)：状态p第i位表示第i+1个插头所在块的连通分量标号(0表示无插头)

hash队列中记录有效状态

state保存原状态，f保存方案数，push(状态,方案数)

shift换行处理，encode最小表示法构造新状态。

DP：

decode解码至code[]，取左和上插头

1.上左

<1>回路：只取最后一格

<2>非回路：合并

2.仅上||仅左

t=上或左连通编号

<1>右无障碍，去右

<2>下无障碍，去下

(可以同时加两个状态)

3.无插头，开新

新连通分量标号13保证不重复。

DP障碍块：直接转移即可(其实我觉得加一下处理可以直接跳过障碍块)

技术分享 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXD=15,HASH=30007,STATE=1000010;
int N,M,maze[MAXD][MAXD],code[MAXD],ch[MAXD],ex,ey;
struct HASHMAP
{
    int head[HASH],next[HASH],size;
    long long state[STATE],f[STATE];
    void init()
     {
         size=0;
         memset(head,-1,sizeof(head));
     }
    void push(long long st,long long ans)
     {
         int h=st&HASH;
         for(int i=head[h];i!=-1;i=next[i])
          if(state[i]==st)
           {
               f[i]+=ans;
               return;
          }
        state[size]=st;
        f[size]=ans;
        next[size]=head[h];
        head[h]=size++;   
     }
}hm[2];
void decode(int *code,int m,long long st)
{
    for(int i=m;i>=0;i--)
     {
         code[i]=st&7;//取后三位！ 
         st>>=3;
     }
}
long long encode(int *code,int m)//根据code编码出新状态st 
{
    int cnt=1;
    memset(ch,-1,sizeof(ch));
    ch[0]=0;
    long long st=0;
    for(int i=0;i<=m;i++)
     {
         if(ch[code[i]]==-1)ch[code[i]]=cnt++;
         code[i]=ch[code[i]];
         st<<=3;
         st|=code[i];
     }
    return st;
}
void shift(int *code,int m)
{
    for(int i=m;i>0;i--)code[i]=code[i-1];
    code[0]=0;
}
void dpblank(int i,int j,int cur)
{
    int left,up;
    for(int k=0;k<hm[cur].size;k++)
     {
         decode(code,M,hm[cur].state[k]);
         left=code[j-1];
         up=code[j];
         if(left&&up)
          {
              if(left==up)
               {
                   if(i==ex&&j==ey)
                    {
                        code[j-1]=code[j]=0;
                        if(j==M)shift(code,M);
                        hm[cur^1].push(encode(code,M),hm[cur].f[k]);
                 }
             }
            else
             {
                 code[j-1]=code[j]=0;
                 for(int t=0;t<=M;t++)
                  if(code[t]==up)code[t]=left;
                 if(j==M)shift(code,M);
                 hm[cur^1].push(encode(code,M),hm[cur].f[k]);
             }
         }
        else if((left&&(!up))||((!left)&&up))
         {
             int t;
             if(left)t=left;else t=up;
             if(maze[i][j+1])
              {
                  code[j-1]=0;
                  code[j]=t;
                  hm[cur^1].push(encode(code,M),hm[cur].f[k]);
             }
            if(maze[i+1][j])
             {
                 code[j-1]=t;
                 code[j]=0;
                 if(j==M)shift(code,M);
                 hm[cur^1].push(encode(code,M),hm[cur].f[k]);
             }
         }
        else
         {
             if(maze[i][j+1]&&maze[i+1][j])
              {
                  code[j-1]=code[j]=13;//比最小表示法极限12多1 
                  hm[cur^1].push(encode(code,M),hm[cur].f[k]);
             }
         }
     }
}
void dpblock(int i,int j,int cur)
{
    for(int k=0;k<hm[cur].size;k++)
     {
         decode(code,M,hm[cur].state[k]);
         code[j-1]=code[j]=0;
         if(j==M)shift(code,M);
         hm[cur^1].push(encode(code,M),hm[cur].f[k]);
     }
}
char str[MAXD];
void init()
{
    memset(maze,0,sizeof(maze));
    ex=0;
    for(int i=1;i<=N;i++)
     {
         scanf("%s",str);
         for(int j=0;j<M;j++)
          {
              if(str[j]==‘.‘)
               {
                   ex=i;ey=j+1;
                   maze[i][j+1]=1;
             }
         }
     }
}
void solve()
{
    int cur=0;
    long long ans=0;
    hm[cur].init();
    hm[cur].push(0,1);
    for(int i=1;i<=N;i++)
     for(int j=1;j<=M;j++)
      {
          hm[cur^1].init();
          if(maze[i][j])dpblank(i,j,cur);
           else dpblock(i,j,cur);
           cur^=1;
      }
    for(int i=0;i<hm[cur].size;i++)
     ans+=hm[cur].f[i];
    printf("%I64d",ans);
}
int main()
{
    while(scanf("%d%d",&N,&M)!=EOF)
     {
         init();
         if(ex==0)
          {
              printf("0\n");
              continue;
         }
        solve();
     }
    return 0;
}
View Code

 

【Ural】1519 Formula 1


联系
我们