首页 > ACM题库 > HDU-杭电 > HDU 4117-GRE Words[解题报告]HOJ
2015
04-16

HDU 4117-GRE Words[解题报告]HOJ

GRE Words

问题描述 :

Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words.
Now George is working on a word list containing N words.
He has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember.
So he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn’t want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word.
Note that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence.
Fruit Ninja

输入:

The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 2 * 104), indicating the number of words.
Then N lines follows, each contains a string Si and an integer Wi, representing the word and its importance. Si contains only lowercase letters.
You can assume that the total length of all words will not exceeded 3 * 105.

输出:

The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 2 * 104), indicating the number of words.
Then N lines follows, each contains a string Si and an integer Wi, representing the word and its importance. Si contains only lowercase letters.
You can assume that the total length of all words will not exceeded 3 * 105.

样例输入:

1
5
a 1
ab 2
abb 3
baba 5
abbab 8

样例输出:

Case #1: 14

/*************************************************************************
    > File Name: hdu4117.cpp
    > Author: X__X
    > Mail: [email protected] 
    > Created Time: 2012/10/10 14:55:19
 ************************************************************************/

#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iostream>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
 
#define MP make_pair
#define PB push_back
#define IT iterator
#define B begin() 
#define E end()
#define X first
#define Y second
#define foreach(it, container) \
    for(typeof((container).begin()) it = (container).begin();it!=(container).end();++it)
#define CLR(a, x) memset(a, x, sizeof (a))
typedef vector<int> VI;
typedef pair<int,int> PII;
VI::IT it;
void op(int n){cout << n << ' ';}

const int inf = 0x3f3f3f3f;
const int maxn = 1e6+10;
const int maxz = 26;
const char _base = 'a';

char g_in[maxn];
int trie[maxn][maxz], fail[maxn], word[maxn];
int dp[maxn], belong[maxn];
int pos[30000];
int npos, n, ans;

void _insert(int s)
{
    int k, p = 0;
    while(g_in[s])
    {
        k = g_in[s] - _base;
        if(trie[p][k] == 0)
        {
            trie[p][k] = ++npos;
            CLR(trie[npos], 0);
            word[npos] = 0;
        }
        p = trie[p][k];
        s++;
    }
}

int q[maxn];
void build_ac()
{
    int t, qe, qs, cur, nt;
    qe = qs = 0;
    for(int i = 0; i < maxz; i++)
        if(t = trie[0][i])
            fail[t] = 0, q[qe++] = t;
    while(qs < qe)
    {
        cur = q[qs++];
        for(int i = 0; i < maxz; i++)
        {
            if(nt = trie[cur][i])
            {
                fail[nt] = trie[fail[cur]][i];
                q[qe++] = nt;
            }
            else
                trie[cur][i] = trie[fail[cur]][i];
        }
    }
}

void cal(int x)
{
    int r, p, t, cur;
    r = p = 0;
    for(int i = pos[x]; i < pos[x+1]; i++)
    {
        cur = g_in[i] - _base;
        p = t = trie[p][cur];
        while(t)
        {
            if(word[t])
                r = max(r, dp[belong[word[t]]]);
            t = fail[t];
        }
    }
    word[p] = p;
    belong[p] = x;
    dp[x] += r;
}

void solve()
{
    scanf("%d", &n);
    npos = pos[0] = 0;
    CLR(trie[0], 0);
    int temp;
    for(int i = 0; i < n; i++)
    {
        scanf("%s%d", g_in + pos[i], &temp);
        pos[i+1] = pos[i] + strlen(g_in + pos[i]);
        _insert(pos[i]);
        dp[i] = temp;
    }
    build_ac();
    ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(dp[i] > 0)
            cal(i);
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
}

int main() 
{
    //freopen("in.txt", "r", stdin); 
    int times;
    scanf("%d", &times);
    for(int i = 0; i < times; i++)
    {
        printf("Case #%d: ", i+1);
        solve();
    }
    return 0;
}

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  4. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。