UOJ Logo root的博客

博客

关于积极使用网站博客系统的倡议。

2017-07-14 14:42:08 By root

强烈建议大家使用博客系统

1. 请将你的题解分享到博客!

2. 请将你的资料分享到博客!

3. 请将你的成长分享到博客!



点击查看ARZhu范例

点击查看markdown常用命令1

点击查看markdown常用命令2

Markdown

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define efo(i,v) for(int i=last[v];i;i=next[i])
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
const int N=1005,mo=1e9+7;
int n,ans,la,lb,f[N][N],nxt[N]['z'+5];
ll g[N][N];
bool bz[N][N];
char a[N],b[N];
ll dfs(int x,int y,int l)
{
    if(l<f[x-1][y-1]) return 0;
    if(x>la+1 || y>lb+1) return 0;
    if(l>=n) return 1;
    int p=nxt[y][a[x]];
    ll t=0;
    if(p && l+1>=f[x][p])
    {
        if(bz[x+1][p+1]) t=(t+g[x+1][p+1])%mo;
        else t=(t+dfs(x+1,p+1,l+1))%mo;
    }
    if(bz[x+1][y]) t=(t+g[x+1][y])%mo;
    else t=(t+dfs(x+1,y,l))%mo;
    g[x][y]=t,bz[x][y]=1;
    return t;
}
int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    scanf("%s\n%s",a+1,b+1);
    la=strlen(a+1),lb=strlen(b+1);
    fd(i,lb,1)
    {
        fo(j,'a','z') nxt[i][j]=(i+1<=lb)?nxt[i+1][j]:(lb+1);
        nxt[i][b[i]]=i;
    }
    fo(i,1,la)
        fo(j,1,lb)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    n=f[la][lb];
    printf("%lld\n",dfs(1,1,0));
    return 0;
}

评论

root
@root 支持
XH_xuxing
![这个文字在图挂了的时候会显示](http://i2.ciimg.com/1949/0a24ed7e8e717cf4.jpg) $\frac{1}{R}=\frac{1}{R1}+\frac{1}{R2}+...+\frac{1}{Rn}$
GongJiaLe
![这个文字在图挂了的时候会显示](http://uoj.ac/pictures/UOJ.ico)
xukuan
比[洛谷](https://www.luogu.org)的markdown好多了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。