首页 > ACM题库 > HDU-杭电 > Hdu 1647 Strategy 待解决 [解题报告] C++
2013
12-21

Hdu 1647 Strategy 待解决 [解题报告] C++

Strategy

问题描述 :

A well known psychology experiment involves people playing a game in which they can either trade with each other or attempt to cheat the other player. If both players TRADE then each gains one point. If one TRADEs and the other CHEATs then the TRADEr loses 2 points and the CHEATer wins 2. If both CHEAT then each loses 1 point.

There are a variety of different strategies for playing this game, although most people are either unable to find a winning strategy, or, having decided on a strategy, do not stick to it. Thus it is fairer to attempt to evaluate these strategies by simulation on a computer. Each strategy is simulated by an automaton. An automaton is characterised by a program incorporating the strategy, a memory for previous encounters and a count reflecting the score of that automaton. The count starts at zero and is altered according to the above rules after each encounter. The memory is able to determine what happened on up to the last two encounters with each other contender.

Write a program that will read in details of up to 10 different strategies, play each strategy against each other strategy 10 times and then print out the final scores. Strategies will be in the form of simple programs obeying the following grammar:

<program> ::= <statement>.
<statement> ::= <command> <ifstat>
<ifstat> ::= IF <condition> THEN <statement> ELSE <statement>
<condition> ::= <cond> <cond> <op> <condition>
<op> ::= AND OR
<cond> ::= <memory> {= #} {<command> NULL}
<memory> ::= {MY YOUR} LAST {1 2}
<command> ::= TRADE CHEAT
Note that LAST1 refers to the previous encounter between these two automata, LAST2 to the encounter before that and that `MY’ and `YOUR’ have the obvious meanings. Spaces and line breaks may appear anywhere in the program and are for legibility only. The symbol `#’ means `is not equal to’. NULL indicates that an encounter has not ocurred. The following are valid programs:

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.

输入:

Input will consist of a series of programs. Each program will be no longer than 255 characters and may be split over several lines for convenience. There will be no more than 10 programs. The file will be terminated by a line containing only a single `#’.

输出:

Output will consist of one line for each line of input. Each line will consist of the final score of the relevant program right justified in a field of width 3.

样例输入:

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.
#

样例输出:

  1
-12
-13


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?