首页 > ACM题库 > HDU-杭电 > hdu 2422 Essay Scoring System待解决[解题报告]C++
2014
01-26

hdu 2422 Essay Scoring System待解决[解题报告]C++

Essay Scoring System

问题描述 :

Professor Binns has finally got tired of scoring essays himself and implemented an automatic essay scoring system to help him screen the numerous essays. Strongly against such an idea, you decided to generate a meaningless essay which can get high mark in his system to prove that his system does not work at all. You’ve obtained the rules used by Binns’s system to score the essay, they’re as follows:
    a)  The word in the essay must be from a particular set of words. If not, the essay will receive a score zero and is automatically rejected.
    b)  Every word in the specified set has a positive integer associated with it, indicating the score the submitter will get for using that word once.
    c)  A word can be used in several different ways; for example, in English, the word “word” can be used as both a noun and a verb. Every occurrence of specific patterns (like verb � adjective � noun) will earn the submitter a particular score.
    In particular, it is allowed for a word to be interpreted in different ways in different patterns.
You’re interested in generating an essay of a specified length with maximum possible score.

输入:

There are multiple test cases in the input file. Each test case starts with three integers N, M and K, (1 <= N <= 100, 0 <= M <= 8, 0 <= K <= 6), the length of the essay to generate, the number of words in the dictionary and the number of patterns, respectively. The following M lines describe the words in the dictionary; each line consists of two integers, Wi, and Ti, (0 <= Wi <= 2000, 1 <= Ti <= 5), representing the score submitter gets every time he/she uses the word, and the number of ways the word can be used. The next part of the input describes the patterns. Each of the K lines describes one pattern, beginning with two integers, Wi, and Ci, (0 <= Wi <= 2000, 1 <= Ci <= 6), indicating the score one can get every time the pattern is used, and the number of consecutive parts in the pattern; followed by Ci integers describing the language parts in the pattern. It is guaranteed that the total number of ways to use a word does not exceed 5; furthermore, the total number of parts contained in all patterns (sum of all Cis) will not exceed 25.
There is a blank line after each test case. Input ends with End-of-File.

输出:

There are multiple test cases in the input file. Each test case starts with three integers N, M and K, (1 <= N <= 100, 0 <= M <= 8, 0 <= K <= 6), the length of the essay to generate, the number of words in the dictionary and the number of patterns, respectively. The following M lines describe the words in the dictionary; each line consists of two integers, Wi, and Ti, (0 <= Wi <= 2000, 1 <= Ti <= 5), representing the score submitter gets every time he/she uses the word, and the number of ways the word can be used. The next part of the input describes the patterns. Each of the K lines describes one pattern, beginning with two integers, Wi, and Ci, (0 <= Wi <= 2000, 1 <= Ci <= 6), indicating the score one can get every time the pattern is used, and the number of consecutive parts in the pattern; followed by Ci integers describing the language parts in the pattern. It is guaranteed that the total number of ways to use a word does not exceed 5; furthermore, the total number of parts contained in all patterns (sum of all Cis) will not exceed 25.
There is a blank line after each test case. Input ends with End-of-File.

样例输入:

2 3 2
4 3 0 1 2
5 2 2 3
1 2 0 4
1 2 1 3
10 2 4 2

2 3 2
4 3 0 1 2
5 2 2 3
1 2 0 4
1 2 1 3
2 2 4 2

样例输出:

Case 1: 16
Case 2: 10 


  1. 那是他爷爷开始搞得 如果三胖想引进外部文化 肯定会对他的政权产生深远的影响 我要是三胖 我也会独大 只是::首先你得是三胖

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count