首页 > 代码库 > English Game

English Game

2024-07-16 02:01:20   219人阅读

题目链接

  • 题意：
    给一个n，一个目标串，之后n行每行一个字符串和一个对应的权值。求，在n个给定的串中选出若干个能组成目标串（每个串可以用多次），得到的权值和最大是多少。
    (1<=n<=1000) and X (the length of goal is not bigger than 10000)，n个串每个长度不超过30
  • 分析：
    比赛时一直想的是，状态：当前匹配到目标串的第几位、用的是哪个串。现在想想真是……明明和【用的是哪个串】这个东西没什么关系，还一直考虑。。
    如果状态只有当前匹配到目标串的第i位，那么转移的话一共有n种情况，每次使用n个串来匹配就得到了转移方程。问题在于，即使采用Hash使得状态转移时候串的匹配复杂度为O（1），这样的复杂度也有len * n从而达到1e7，对于多组数据是不可行的
    问题的关键在于想到状态转移时候的特点：这时候对于目标串是一样的，用这个串去匹配n个串，看一下是否能完全匹配。这时候有一个明显的特点，对于匹配成功的这些串，必然会有共同的公共前缀！也就是说，很多比较是可以优化掉的，这时候就应该想到trie树来解决了。
const int MAXLEN = 11000;

char ipt[MAXN][50], goal[MAXLEN];
int val[MAXN],  len[MAXN], ans[MAXN];
int dp[MAXLEN];

const int maxm = 31000;
struct Trie
{
    int numptr;
    struct Node
    {
        Node* son[26];
        int ptr;
        void init()
        {
            CLR(son, (int)NULL);
            ptr = -1;
        }
    } s[maxm], root;

    void init()
    {
        numptr = 0;
        root.init();
    }

    void ins(char *ch, int z)
    {
        Node* ptr = &root;
        for(int i = 0; ch[i] != 0; i++)
        {
            int x = ch[i] - 'a';
            if(ptr->son[x] == NULL)
            {
                s[numptr].init();
                ptr->son[x] = &s[numptr++];
            }
            ptr = ptr->son[x];
        }
        ptr->ptr = z;
    }

    int find(char *ch)
    {
        int cnt = 0;
        Node *ptr = &root;
        for(int i = 0; ch[i] != 0; i++)
        {
            if (ptr->ptr != -1)
                ans[cnt++] = ptr->ptr;
            int x = ch[i] - 'a';
            if(ptr->son[x] == NULL)
            {
                return cnt;
            }
            ptr = ptr->son[x];
        }
        if (ptr->ptr != -1)
            ans[cnt++] = ptr->ptr;
        return cnt;
    }
} trie;

int main()
{
    int n;
    while (~scanf("%d%s", &n, goal + 1))
    {
        trie.init();
        CLR(dp, -1); dp[0] = 0;
        FE(i, 1, n)
        {
            scanf("%s%d", ipt[i] + 1, &val[i]);
            len[i] = strlen(ipt[i] + 1);
            trie.ins(ipt[i] + 1, i);
        }
        int l = strlen(goal + 1);
        FE(i, 0, l - 1)
        {
            if (dp[i] == -1)
                continue;
            int cnt = trie.find(goal + i + 1);
            REP(j, cnt)
            {
                int ind = ans[j];
                int nxt = len[ind] + i;
                if (dp[nxt] < dp[i] + val[ind])
                    dp[nxt] = dp[i] + val[ind];
            }
        }
        WI(dp[l]);
    }
    return 0;
}


联系
我们