乘法表问题

乘法表问题

时间： 1ms        内存：64M

描述：

定义于字母表S={a,b,c}上的乘法表如下

依此乘法表，对任一定义于S上的字符串，适当加括号后得到一个表达式。例如，对于字符串x=bbbba，它的一个加括号表达式为(b(bb))(ba)。依乘法表，该表达式的值为a。试设计一个动态规划算法，对任一定义于∑上的字符串x=x₁x₂……x_n  ，计算有多少种不同的加括号方式，使由x 导出的加括号表达式的值为a。

对于给定的字符串x=x₁x₂……x_n ，计算有多少种不同的加括号方式，使由x导出的加括号表达式的值为a。

输入：

输入数据只有1 行，给出一个字符串。

输出：

输出数据只有1 个数，表示计算出的加括号方式数。

示例输入：

bbbba

示例输出：

6

提示：

参考答案（内存最优[1724]）：

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 101
#define ll long long
using namespace std;
ll sum[MAX][MAX][3];
char str[MAX];
ll dfs(int l,int r)
{
    if(sum[l][r][0])return sum[l][r][0];
    if(l==r)
    {
        sum[l][r][str[l]-'a']=1;
        return sum[l][r][0];
    }
    else
    {
        ll t=0;
        ll ta,tb,tc;
        ta=tb=tc=0;
        for(int i=l;i<r;i++)
        {
            t+=dfs(l,i)*dfs(i+1,r);
            ta+=sum[l][i][2]*sum[i+1][r][0]+sum[l][i][1]*sum[i+1][r][2]+sum[l][i][0]*sum[i+1][r][2];
            tb+=sum[l][i][0]*sum[i+1][r][0]+sum[l][i][0]*sum[i+1][r][1]+sum[l][i][1]*sum[i+1][r][1];
            tc+=sum[l][i][1]*sum[i+1][r][0]+sum[l][i][2]*sum[i+1][r][1]+sum[l][i][2]*sum[i+1][r][2];
        }
        sum[l][r][0]=ta,sum[l][r][1]=tb,sum[l][r][2]=tc;
    }
    return sum[l][r][0];
}
int main()
{
    int n;
    cin>>str;
    n=strlen(str);
    cout<<dfs(0,n-1)<<endl;
    return 0;
}

参考答案（时间最优[32]）：

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 101
#define ll long long
using namespace std;
ll sum[MAX][MAX][3];
char str[MAX];
ll dfs(int l,int r)
{
    if(sum[l][r][0])return sum[l][r][0];
    if(l==r)
    {
        sum[l][r][str[l]-'a']=1;
        return sum[l][r][0];
    }
    else
    {
        ll t=0;
        ll ta,tb,tc;
        ta=tb=tc=0;
        for(int i=l;i<r;i++)
        {
            t+=dfs(l,i)*dfs(i+1,r);
            ta+=sum[l][i][2]*sum[i+1][r][0]+sum[l][i][1]*sum[i+1][r][2]+sum[l][i][0]*sum[i+1][r][2];
            tb+=sum[l][i][0]*sum[i+1][r][0]+sum[l][i][0]*sum[i+1][r][1]+sum[l][i][1]*sum[i+1][r][1];
            tc+=sum[l][i][1]*sum[i+1][r][0]+sum[l][i][2]*sum[i+1][r][1]+sum[l][i][2]*sum[i+1][r][2];
        }
        sum[l][r][0]=ta,sum[l][r][1]=tb,sum[l][r][2]=tc;
    }
    return sum[l][r][0];
}
int main()
{
    int n;
    cin>>str;
    n=strlen(str);
    cout<<dfs(0,n-1)<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。