首页 > ACM题库 > HDU-杭电 > HDU 3886-Final Kichiku “Lanlanshu”-动态规划-[解题报告]HOJ
2015
04-13

HDU 3886-Final Kichiku “Lanlanshu”-动态规划-[解题报告]HOJ

Final Kichiku “Lanlanshu”

问题描述 :

During 2010 summer training, temperlisyer often does problem like this:
“Consider a decimal integer as sequence of digits {D0, D1 … Dn-1} (D0 > 0), if exists such x, y and z, satisfying:
1.Di-1<Di (0<i<=x)
2.Di-1=Di (x<i<=y)
3.Di-1<Di (y<i<=z)
4.Di-1>Di (z<i<=n-1)

We call this integer “Lanlanshu”, now give you two numbers A and B, calculate how many “Lanlanshu” are in [A, B].“
He solved so many of these and finally get bored, and then get crazy! He decided to make up a problem to put this type of problems to an end.
Give you a string str consists only by ‘/’, ‘-‘ and ‘\’, and its length is l. Consider a decimal integer as sequence of digits {D0, D1 … Dn-1} (D0 > 0), define x0=0, xl=n-1, if exists such x1, x2…xl (x0 < x1 < x2 < … < xl) satisfying:
1. If str[i]=’/’, Dj-1<Dj (xi<j<=xi+1)
2. If str[i]=’-’, Dj-1=Dj (xi<j<=xi+1)
3. If str[i]=’\’, Dj-1>Dj (xi<j<=xi+1)

We call it Final Kichiku “Lanlanshu”, now give you two numbers A and B, calculate how many Final Kichiku “Lanlanshu” are in [A, B]. This number maybe huge, we only want to now the last 8 digits of the result.

输入:

Multiple cases (no more than 100), for each case:
The first line is string str, length is below 100.
The second line contains two integers A and B (0≤Ai≤Bi≤10^100).
Input terminates by EOF.

输出:

Multiple cases (no more than 100), for each case:
The first line is string str, length is below 100.
The second line contains two integers A and B (0≤Ai≤Bi≤10^100).
Input terminates by EOF.

样例输入:

/\
01221 2012

样例输出:

00000315

 

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3886

题意:给一定区间[A,B],一串由/,\,-组成的符号串。求满足符号串的数字个数。

•/表示数字从左到右递增
•\表示数字从左到右递减
•-表示数字从左到右相等
分析:dp[i][j][k],表示当枚举到第i位的数,匹配str[j],前一位是k,满足要求的数字个数.
 
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int dp[110][110][10];
int dig[110],len;
char str[110],a[110],b[110];
int judge(int i,int pre,int now)
{
    if(str[i]=='/')return pre<now;
    else if(str[i]=='-')return pre==now;
    else if(str[i]=='\\')return pre>now;
}
int  dfs(int pos,int cur,int pre,int limit,int fzore)
{
    if(!pos)return cur==len;
    if(!limit&&~dp[pos][cur][pre])return dp[pos][cur][pre];
    int ed=limit?dig[pos]:9;
    int ans=0;
    for(int i=0;i<=ed;i++)
    {
        if(!fzore)
        {
            if(cur<len&&judge(cur,pre,i))
            ans+=dfs(pos-1,cur+1,i,limit&&i==ed,fzore&&!i);
            //这里为什么能往回走,因为如果pre,i满足str[cur-1],同时
            //已经知道“pre前一位,pre”也满足str[cur-1],这样还是满足要求的数
            //例如数据123455555554321是符合/-\的,5之前都是/,中间都是-,后面都是\。
            else if(cur&&judge(cur-1,pre,i))
            ans+=dfs(pos-1,cur,i,limit&&i==ed,fzore&&!i);
        }
        else ans+=dfs(pos-1,cur,i,limit&&i==ed,fzore&&!i);
        ans%=mod;
    }
    if(!limit)dp[pos][cur][pre]=ans;
    return ans;
}
int solve(char s[],bool left)
{
    int lens=strlen(s),m=0,i=0;
    while(s[i]=='0'&&i<lens)i++;
    for(int j=lens-1;j>=i;j--)dig[++m]=s[j]-'0';
    if(left&&m)
    {
        for(int i=1;i<=m;i++)
        {
            if(dig[i])
            {
                dig[i]--;break;
            }
            else dig[i]=9;
        }
    }
    return dfs(m,0,0,1,1);
}
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        len=strlen(str);
        scanf("%s%s",a,b);
        memset(dp,-1,sizeof(dp));
        printf("%08d\n",((solve(b,0)-solve(a,1))+mod)%mod);
    }
}

 

参考:http://www.cnblogs.com/lienus/p/4249310.html


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。