计数dp-hdu-4054-Number String-白红宇

计数dp-hdu-4054-Number String

阅读量：5102 次

发布时间：2019-06-13

本文共 2067 字，大约阅读时间需要 6 分钟。

题目链接：

题目大意：

给一个只含‘I','D','?'三种字符的字符串，I表示当前数字大于前面的数字，D表示当前的数字小于前面一位的数字，？表示当前位既可以小于又可以大于。

问1~n的排列中有多少个满足该字符串。

解题思路：

计数dp.

dp[i][j]表示长度为i字符串，最后一个数为j时，能达到满足给定字符串的1~i+1的排列个数。

转移方程：

当S[i]='I'时，当前如果为j的话，前面的一位肯定要小于j,dp[i][j]+=Mi[j-1] ; //Mi[i]表示前面一位下标小于等于i dp[][1~i]的和

当S[i]='D'时，dp[i][j]+=(la-Mi[j-1]); //前一位要大于等于j

当S[i]='?'时，dp[i][j]+=la; //la表示前一位所有的状态总和.

注意递推的时候，前i位只和相对大小有关，与绝对大小无关，所以都用1~i表示，当增加一位时，就变成了1~i+1，如果当前为j,前面的小于j的状态不变，大于等于j的状态k所表示的值现在表示k+1的值，这样就从1~i等价的转化成了1~i+1,这样考虑就不用考虑1~n的放法了，递推到n位时肯定都是1~n了。

代码：

#include 
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;const int INF = 0x3f3f3f3f;const double eps = 1e-6;const double PI = acos(-1.0);typedef __int64 ll;//#pragma comment(linker, "/STACK:1024000000,1024000000")/*freopen("data.in","r",stdin);freopen("data.out","w",stdout);*/#define M 1000000007#define Maxn 1100char sa[Maxn];int dp[Maxn][Maxn]; //dp[i][j]表示有i个字符，当前数字为j时，所有的总数 //注意有i个字符说明前面一共有1~i+1个不同的数字，dp[i-1]共有1~i个数字， //建立递推时，如果当前为j，则前面小于j的不变，大于等于j的全部加一，这样就从1~i变成了1~i+1int la;int Mi[Maxn][2]; //Mi[i]表示上一个dp[i-1]下标小于等于j的值的总和int main(){ while(~scanf("%s",sa+1)) { int len=strlen(sa+1); for(int i=0;i<=len+10;i++) //初始化 { Mi[i][0]=Mi[i][1]=0; for(int j=0;j<=len+10;j++) dp[i][j]=0; } dp[0][1]=1; //没有字符时，有一个数 且这个数为1 la=1; Mi[1][0]=1; //下标小于等于1的有一个 int pp=0; for(int i=1;i<=len;i++) { pp=pp^1; //当前状态 int n=i+1;//当前为可能的取值，注意前面的之和相对大小有关 ll cur=0; for(int j=1;j<=n;j++) //枚举当前位的数值 { if(sa[i]=='I') //如果为增的话，前面的肯定是小于j的 dp[i][j]=(dp[i][j]+Mi[j-1][pp^1])%M; else if(sa[i]=='D') //减的话,前面是大于等于j的，加1后就变成了大于j的了 dp[i][j]=(dp[i][j]+(la-Mi[j-1][pp^1])%M+M)%M; else //如果无所谓的话，前面所有1-n-1个状态都行 dp[i][j]=(dp[i][j]+la)%M; //用一个la记录 Mi[j][pp]=(Mi[j-1][pp]+dp[i][j])%M;//求出当前的Mi cur=(cur+dp[i][j])%M; //求出当前的la } la=cur; //这题卡常数，多了几个循环都不行 } ll ans=0; for(int i=1;i<=len+1;i++) //枚举最后的能够占有的值 ans=(ans+dp[len][i])%M; printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/suncoolcat/p/3297225.html

你可能感兴趣的文章

tomcat启动后，页面浏览时报错 Unable to compile class for JSP的解决方案