首页 > ACM题库 > HDU-杭电 > HDU 3136-Taunt Generation Simulator-动态规划-[解题报告]HOJ
2014
03-03

HDU 3136-Taunt Generation Simulator-动态规划-[解题报告]HOJ

Taunt Generation Simulator

问题描述 :

In all the annals of knighthood, no personality trait has been in more dire need than the fortitude to withstand the diplomatically deleterious effects of a vicious, relentless taunting. Tasked with strengthening the mental endurance of Camelot’s knights, King Arthur’s court decided that instructional taunting must be applied, yet it could not be delivered by the chivalrous administration. Thus, Sir Lancelot commanded a local anarcho-syndicalist peasant to write a program that generates taunts (a.k.a. mudslinging) thereby producing a script to test the patience of knights in a training environment. To prevent unbridled creativity in taunting from spoiling the otherwise stately proceedings of a nobleman’s education, the following rules designed by committee (The Round Table) must be adhered to:

<taunt> ::= <sentence> | <taunt> <sentence> | <noun>! | <sentence>
<sentence> ::= <past-rel> <noun-phrase> | <present-rel> <noun-phrase> | <past-rel> <article> <noun>
<noun-phrase> ::= <article> <modified-noun>
<modified-noun> ::= <noun> | <modifier> <noun>
<modifier> ::= <adjective> | <adverb> <adjective>
<present-rel> ::= your <present-person> <present-verb>
<past-rel> ::= your <past-person> <past-verb>
<present-person> ::= steed | king | first-born
<past-person> ::= mother | father | grandmother | grandfather | godfather
<noun> ::= hamster | coconut | duck | herring | newt | peril | chicken | vole | parrot | mouse | twit
<present-verb> ::= is | “masquerades as”
<past-verb> ::= was | personified
<article> ::= a
<adjective> ::= silly | wicked | sordid | naughty | repulsive | malodorous | ill-tempered
<adverb> ::= conspicuously | categorically | positively | cruelly | incontrovertibly

Note that all phrases in double quotes are to be treated as one word for taunt simulation output.

The number of taunts elicited at any given time is derived from the number of words spoken by the knight. For every three words (or fraction thereof) delivered by the knight, the generator produces one or more taunts in a theater-style script format. In the event that 2 taunts must be produced on a single line, they will be counted as 2 taunts towards the total required. By a mandate from the masses, a word will always contain at least one alphabetic character, and will be separated from other words by at least 1 space.

In exception to the above rules, whenever the program finds the holy grail, which is to say, the letters t-h-e-h-o-l-y-g-r-a-i-l (case insensitive) in that order in a line of input, then the first taunt generated will be displayed by the program as "(A childish hand gesture)".

To ensure all royal quality assurance criteria are met, the program must be demonstrated by a simulation showing the taunts produced from a series of inputs. Each taunt is generated by applying the taunt generation rules until all of the <…> have been replaced with appropriate words. In most cases, you will face a choice of alternate rules for expanding a phrase name. In these cases, you should make a choice as follows: Suppose that this is the kth such choice that you have faced for that rule since the start of program execution, and that you must choose one of n rules for expanding a given kind of phrase. Let the rules for that phrase be numbered from 1…n in the order of appearance above, and then choose rule number ((k-1) mod n) + 1.

Well, get on with it!

输入:

The input will consist of an unspecified number of lines. Each line will contain a statement uttered by a knight consisting of letters, digits, the characters ",.-!?" and whitespace. Each line of input will be more than 1 character and less than 72 characters in length. All words will be separated by whitespace. Each statement will contain at least one word.

输出:

The input will consist of an unspecified number of lines. Each line will contain a statement uttered by a knight consisting of letters, digits, the characters ",.-!?" and whitespace. Each line of input will be more than 1 character and less than 72 characters in length. All words will be separated by whitespace. Each statement will contain at least one word.

样例输入:

Hello!
Are you feeling alright?
Is there someone else I could talk to?
Anyone at all?
We seek the holy grail . . .

样例输出:

Knight: Hello!
Taunter: Your mother was a hamster.

Knight: Are you feeling alright?
Taunter: Coconut! Your steed is a silly duck.

Knight: Is there someone else I could talk to?
Taunter: Your father personified a herring.
Taunter: Your grandmother was a newt.
Taunter: Peril! Your king masquerades as a conspicuously wicked chicken.

Knight: Anyone at all?
Taunter: Your grandfather personified a vole.

Knight: We seek the holy grail . . .
Taunter: (A childish hand gesture).
Taunter: Your godfather was a parrot.

本题练习快速排序和动态规划。

题目连接:

http://acm.hit.edu.cn/hoj/problem/view?id=3136

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define Maxn 5002

int be[Maxn];//开始时刻
int en[Maxn];//结束时刻
int pri[Maxn];//优先级
int best[Maxn];//the maximum total value of beauty level

//快速排序,以en[i]升序排列
void qsort(int l,int r)
{
    int x = en[rand()%(r-l+1) + l];//+l
    int i = l;
    int j = r;
    while(i<=j)
    {
        while(en[i]<x)
        {
            i++;
        }
        while(en[j]>x)
        {
            j--;
        }
        if(i<=j)
        {
            swap(be[i],be[j]);
            swap(en[i],en[j]);
            swap(pri[i],pri[j]);
            i++;
            j--;
        }
    }
    if(l<j)
    {
        qsort(l,j);
    }
    if(i<r)
    {
        qsort(i,r);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int ans = 0;
        for(int i=0; i<n; i++)
        {
            scanf(" %d %d %d",&be[i],&en[i],&pri[i]);
            en[i] = en[i] + be[i] - 1;
        }
        qsort(0,n-1);
        for(int i=0; i<n; i++)
        {
            best[i] = pri[i];
        }
        for(int i=0; i<n; i++)
        {
            for(int j=i-1; j>=0; j--)
            {
                if(be[i]>en[j])
                {
                    best[i] = max(best[i],best[j] + pri[i]);
                }
            }
        }
        for(int i=0; i<n; i++)
        {
            if(best[i]>ans)
            {
                ans = best[i];
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}

参考:http://blog.csdn.net/niuox/article/details/8469017


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。