题解 CF115D 【Unambiguous Arithmetic Expression】

Vn_nV · 2019-03-28 22:03:27 · 题解

方法1：朴素区间dp（非标算）

看到这道题，许多人的第一反应就是区间dp。dp(i,j)表示处理完i-j这个区间的方案数。

看下数据范围n<=2000。区间dp时间复杂度n^3，也就是8e9。

如果直接写就会TLE，因为有很多无效状态。如果提前处理掉，会使程序快不少，再加上一些卡常，就可以过了。

code:

#include<bits/stdc++.h>
using namespace std;
const int md=1000003;
int f[2222][2222];
int a[2222],x[2222],y[2222],st[2222];
int main()
{
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int n=s.length();
    for(int i=0;i<n-1;i++)
    {
        if(s[i]<'0'||s[i]>'9')
        {
            if(s[i+1]=='*'||s[i+1]=='/')
            {
                cout<<0<<endl;
                return 0;
            }
        }
    }
    if(s[0]=='*'||s[0]=='/')
    {
        cout<<0<<endl;
        return 0;
    }
    int m=0,t=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]<'0'||s[i]>'9')
            t++;
        else if(t||i==0)
        {
            a[m]=t-1;
            m++;
            t=0;
        }
    }
    a[0]++;
    if(t)
    {
        cout<<0<<endl;
        return 0;
    }
    n=0;
    for(int i=0;i<m;i++)
    {
        st[i]=n;
        for(int j=a[i];j>=0;j--)
        {
            x[n]=i;
            y[n]=j;
            n++;
        }
    }
    long long g;
    for(int i=n-1;i>=0;i--)
    {
        f[i][x[i]]=1;
        for(int j=x[i]+1;j<m;j++)
        {
            if(y[i]>0)
                f[i][j]=f[i+1][j];
            else
                f[i][j]=0;
            g=0;
            for(int k=x[i];k<j;k++)
                g+=(long long)f[i][k]*f[st[k+1]][j];
            f[i][j]=(f[i][j]+g)%md;
        }
    }
    cout<<f[0][m-1]<<endl;
    return 0;
}

方法2：更改dp状态（标算）

dp1(i,j)表示考虑到第i个空位还有j个左括号没匹配，且最后一个括号为左括号。

dp2(i,j)表示考虑到第i个空位还有j个左括号没匹配，且最后一个括号为右括号。

具体转移参见代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2100;
char txt[N];
string presolve(string s)
{
    string res;
    int n=s.size();
    int i=0;
    while(i<n)
    {
        if(s[i]=='+'||s[i]=='-')
        {
            res+='+';
            i++;
            continue;
        }
        if(s[i]=='*'||s[i]=='/')
        {
            res+='*';
            i++;
            continue;
        }
        res+='x';
        while(i<n&&isdigit(s[i]))
            i++;
    }
    return res;
}
const int mod=1000003;
int dp1[N][N],dp2[N][N];
int main()
{
    scanf("%s",txt);
    string s=presolve(txt);
    if(s=="x")
    {
        cout<<1<<endl;
        return 0;
    }
    dp1[0][0]=1;
    int n=s.size();
    for(int i=0;i<=n;i++)
    {
        for(int j=N-1;j>=0;j--)
        {
            if(dp2[i][j])
            {
                dp1[i+1][j+1]=(dp1[i+1][j+1]+dp2[i][j])%mod;
                if(j>0)
                    dp2[i][j-1]=(dp2[i][j-1]+dp2[i][j])%mod;
            }
        }
        for(int j=0;j<N;j++)
        {
            if(dp1[i][j])
            {
                if(s[i]=='+')
                    dp1[i+1][j+1]=(dp1[i+1][j+1]+dp1[i][j])%mod;
                if(s[i]=='x')
                    dp1[i+2][j+1]=(dp1[i+2][j+1]+dp1[i][j])%mod;
                if(s[i]=='x'&&j>0)
                    dp2[i+1][j-1]=(dp2[i+1][j-1]+dp1[i][j])%mod;
            }
        }
    }
    cout<<dp2[n][0]<<endl;
    return 0;
}