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

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

poj 3208构造有限状态自动机进行dp转移  

2013-09-22 22:00:00|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

//题目要识别连续3个6,可构造自动机,总共只需4个状态,
// 0 状态最后一个不是6 且已经输入的串里面没有三个连续的6
// 1 状态最后含有一个6,倒数第二个不是6,且已经输入的串里面没有三个连续的6
// 2 两个6,倒数第三个不是6 且已经输入的串里面没有三个连续的6
// 3 状态已经输入了三个6
// (0)-----6----->(1)-----6----->(2)-----6------>(3)-----任何数字----->(3)
// 没有写出来的都是转移到状态 (0)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 15       //最大长度
#define maxlen 10    //每个节点的出发数目
#define maxv 4         //状态数

int trie[maxv][maxlen];    //trie[i][j]表示从i节点沿路径j到达的节点号
int dp[maxn][maxv];       //dp[i][j]表示有i步可走,当前在状态j的种类
int n,ans[maxn],tot;

void init(){
   int i,j,k,tem;
   memset(trie,0,sizeof(trie));
   trie[0][6]=1; trie[1][6]=2; trie[2][6]=3;
   for (i=0; i<=9; i++)     //自动机上的初始化
      trie[3][i]=3;
   memset(dp,0,sizeof(dp));
   dp[0][3]=1;
   dp[1][2]=1; dp[1][3]=10;   //dp的初始化
   for (i=2; i<maxn; i++)
      for (j=0; j<maxv; j++)
         for (k=0; k<=9; k++){
           tem=trie[j][k];
          dp[i][j]+=dp[i-1][tem];
         }
}

int main(){
   int i,j,tem,T,sum,pos,num;
   init();
   scanf("%d",&T);
   while (T--){
      scanf("%d",&n);
      for (i=1; i<maxn; i++)
         if (dp[i][0]>=n) break;     //查找需要的长度
      pos=tot=0;                        //pos为到了哪个节点
      for (num=i; num; num--){
         sum=0;
         for (j=0; j<=9; j++){
            tem=trie[pos][j];
            if (sum+dp[num-1][tem]<n)      //sum用于试加
                sum+=dp[num-1][tem];
            else break;
        }
        ans[++tot]=j;   

        n-=sum;
        pos=tem;
     }
     for (i=1; i<=tot;)     //跳掉前缀的0
     if (ans[i]==0) i++;
     else break;
     for (; i<=tot; i++)
     printf("%d",ans[i]);
     printf("\n");
   }
 return 0;
}

  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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