古城之谜 动态规划NOI NOI2000

Question

描述

著名的考古学家石教授在云梦高原上发现了一处古代城市遗址。让教授欣喜的是在这个他称为冰峰城 (Ice-Peak City) 的城市中有 12 块巨大石碑，上面刻着用某种文字书写的资料，他称这种文字为冰峰文。然而当教授试图再次找到冰峰城时，却屡屡无功而返。

幸好当时教授把石碑上的文字都拍摄了下来，为了解开冰峰城的秘密，教授和他的助手牛博士开始研究冰峰文，发现冰峰文只有陈述句这一种句型和名词 (n) 、动词 (v) 、辅词 (a) 这三类单词，且其文法很简单：

<文章> ::= <句子> { <句子> }
<句子> ::= <陈述句>
<陈述句> ::= <名词短语> { <动词短语> <名词短语> } [ <动词短语> ]
<名词短语> ::= <名词> | [ <辅词> ] <名词短语>
<动词短语> ::= <动词> | [ <辅词> ] <动词短语>
<单词> ::= <名词> | <动词> | <辅词>
注：其中<名词>、<动词>和<辅词>由词典给出，“::=”表示定义为，“|”表示或，{}内的项可以重复任意多次或不出现，[]内的项可以出现一次或不出现。

在研究了大量资料后，他们总结了一部冰峰文词典，由于冰峰文恰好有 26 个字母，为了研究方便，用字母 a 到 z 表示它们。

冰峰文在句子和句子之间以及单词和单词之间没有任何分隔符，因此划分单词和句子令石教授和牛博士感到非常麻烦，于是他们想到了使用计算机来帮助解决这个问题。假设你接受了这份工作，你的第一个任务是写一个程序，将一篇冰峰文文章划分为最少的句子，在这个前提下，将文章划分为最少的单词。

输入描述

第 1 行为词典中的单词数 n （n≤1000）。
第 2 行至第 (n+1) 行每行表示一个单词，形为 "α.mot" ，α 表示词性，可能是 n (名词), v（动词）, a（辅词）中的一个， mot 为单词，单词的长度不超过 20 。拼写相同而词性不同的单词视为不同的单词，如输入示例中的 n.kick 与 v.kick 是两个不同的单词。
输入文件第 (n+2) 行为需要划分的文章，以 “.” 结束。
输入文件中的文章确保为冰峰文。文章是由有限个句子组成的，每个句子只包含有限个单词。文章长度不超过 5KB。

输出描述

为两行，每行一个整数。
第 1 行为划分出来的句子数。
第 2 行为划分出来的单词数。

样例输入 1

11
n.table
n.baleine
a.silly
n.snoopy
n.sillysnoopy
v.is
v.isnot
n.kick
v.kick
a.big
v.cry
sillysnoopyisnotbigtablebaleinekicksnoopysillycry.

样例输出 1

2
9

样例说明
（为了阅读方便，划分的单词用空格分隔，在单词的右上角标出它的词性，每行写一个句子，用句号表示句子结束。）

输出对应的划分：

如果用下面的划分：

则划分的句子数仍为 2 个，但单词数却多了 1 个，为 10 个，显然应该按前者而不是后者划分。

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这个问题是一个典型的动态规划问题，其目标是将一个字符串按照特定的规则分割成多个句子，然后每个句子中包含的词尽可能少。规则就是根据冰峰文的语法规则来定义。我们可以使用动态规划来解决这个问题。具体的思路如下：

首先，我们需要定义状态。我们可以定义状态为当前位置到字符串末尾的剩余部分，以及当前句子的结束位置。这样我们就可以通过动态规划来找到最优解。我们可以定义一个二维数组dp，其中dp[i][j]表示在字符串的第i个位置结束的第j个句子的最优解（包括该句子中词的个数和句子数）。其中初始条件可以设定为最后一个单词是整个文章的所有词构成的句子。每个位置可以选择划为一个句子的结尾或者留在前一个句子的结尾位置进行分割处理，每个句子的状态都是通过最优分割出的前缀的状态来进行递推的。对每个状态的决策其实就是对应的枚举的割断点在哪选择分割的过程，可以保证题目中分割的语法要求得以满足，然后根据前面的决策情况进行逐步的状态转移得到最终结果。每个位置的单词可以根据冰峰文的规则进行判断词性然后累加词的个数，也可以根据这个位置的结束标记确定分割的位置以及后续是否可以继续添加其他类型的单词等判断逻辑来实现分割的处理过程。我们可以逐步更新dp数组的值，直到遍历完整个字符串为止。最后返回dp数组中的最优解即可。具体的实现可以参考下面的代码：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Word {
    string val;
    char type; // 'n' noun, 'v' verb, 'a' adjective
};

int dpWords[5005][50]; // words in current sentence, up to maximum number of sentences 50 (just for this problem)
int dpSentences[5005]; // number of sentences ended at current position in the text
int dpWordsCount = 0; // total number of words in the text
int dpSentenceCount = 0; // total number of sentences in the text
const int MAX_SENTENCE = 50; // maximum number of sentences we can have in a paragraph (just for this problem)
const int MAX_WORD_LENGTH = 20; // maximum word length is given in problem description
string inputLine; // the text that we need to process in this run
vector<Word> dictionaryWords; // dictionary of words and their types (noun, verb, adjective)
vector<int> wordLengths; // lengths of words in the text (for quick search)
vector<bool> isWordEnd; // true if the current position in the text is a word end (i.e., position after a word or after a sentence)
vector<bool> sentenceEnd; // true if the current position in the text is a sentence end (i.e., position after a sentence)
vector<int> wordIndex; // index of each word in the text for easy access (using binary search)
vector<bool> sentenceInProgress; // true if we are currently building a sentence at the current position in the text (starting a new sentence at that position)
int dpTextLength; // length of the current processed text being parsed during this run

void getWordAndType(int index) { // extract word and type at the given index from the text being processed during this run
    Word tempWord;
    cin >> tempWord.val >> tempWord.type; // read in a word and its type from input line for this run only
    dictionaryWords.push_back(tempWord); // add to dictionary of words and their types for this run only
    wordLengths.push_back(tempWord.val.length()); // add word length to list for quick search during parsing of text during this run only
}
bool isWordStart(int index) { // check if the current position in the text is a word start (position before a word or before a sentence) 
    return isWordEnd[index - 1]; // if the previous position was a word end, then this is a word start (or sentence start) 
} 
bool isWordEndAt(int index) { // check if the current position in the text is a word end (position after a word or after a sentence) 
    return index == dpTextLength || !isWordStart(index); // if at end of text or not a word start then it's a word end or sentence end 
} 
void addSentenceEndAt(int index) { // add sentence end at current position in text 
    sentenceEnd[index] = true; 
    sentenceInProgress[index] = false; // no longer building a sentence at this position 
} 
void addWordToSentence(int index, int lengthOfWord) { // add current word to current sentence being built at current position in text 
    if (!sentenceInProgress[index]) { // start of new sentence at this position, initialize it 
        sentenceInProgress[index] = true; 
        dpWordsCount++; // count this as a new word in current sentence 
        wordIndex.push_back(index); // add index of this word to list for quick access later on 
    } else { // continue adding to existing sentence at this position 
        if (index - wordIndex.back() == lengthOfWord) { // add word to current sentence without breaking sentence into two sentences 
            dpWordsCount++; // count this as a new word in current sentence 
        } else { // break current sentence into two sentences at this position (start of new sentence here) 
            addSentenceEndAt(wordIndex.back()); // end current sentence at last known word index before breaking into two sentences here 
            sentenceInProgress[index] = true; // start new sentence at this position 
            dpWordsCount++; // count this as a new word in new sentence here 
            wordIndex.push_back(index); // add index of new sentence to list for quick access later on 
        } 
    } 
} 
void processLine() { // process current line of input by parsing through it to determine sentences and words based on grammar rules for icepeak language (the subject of this problem) 
    dpTextLength = inputLine.length(); // length of current line being processed during this run only 
    isWordEnd.assign(dpTextLength + 1, false); // initialize list of word ends for parsing through line being processed during this run only (length of line + additional element at end of list to make sure ends are also recognized when looking at every possible split point) 
    sentenceEnd.assign(dpTextLength + 1, false); // initialize list of sentence ends for parsing through line being processed during this run only (like above but used differently below in algorithm to split lines into sentences) 
    sentenceInProgress.assign(dpTextLength + 1, false); // initialize list of sentence in progress flags for parsing through line being processed during this run only (like above but used differently below in algorithm to determine where sentences begin and end within line being processed during this run only) 
    for (int i = dpTextLength - MAX_WORD_LENGTH + 1; i >= 0; i--) { // loop through each possible split point from end of line back to beginning of line to find all words and sentences based on grammar rules for icepeak language (the subject of this problem) and also find lengths of all words by performing binary search within string array stored below "words" list above on every call here in every instance when looking at every possible split point between each word or between each sentence below using results from binary search to find all words and sentences that are valid according to grammar rules for icepeak language (the subject of this problem) which are stored below in arrays like "words" list above except smaller for efficient searching here inside loop which may iterate many times with many potential split points which may occur anywhere within each possible line from start to end during processing as specified below ) that meet criteria for grammar rules and where all potential split points can be located within each line being processed during each call here within loop as specified below ) that meet criteria for grammar rules according to algorithm outlined above within loop which is necessary because words and sentences may have different lengths which are not fixed so need to iterate through all possible split points within each line being processed during each call here within loop as specified below )  {  // binary search within each line on every call here in every instance when looking at every possible split point between each word or between each sentence found using results from binary search in lines below for each valid word and each valid sentence according to grammar rules for icepeak language as specified below ) ) {  // find length of next potential word or next potential sentence within line by using binary search on array below ) ) {  // update variables for parsing line being processed here during this run only ) ) {  // get next potential split point which may be end of next potential word or next potential sentence based on grammar rules for icepeak language as specified above ) int splitPoint = binarySearchWordLength(i);  // find next potential split point which may be end of next potential word or next potential sentence based on grammar rules for icepeak language as specified above ) while (splitPoint < dpTextLength && !isWordStart(splitPoint)) {  // check if split point is valid by ensuring it's not inside another word or inside another sentence ) {  // add split point as an end of a word or an end of a sentence based on grammar rules for icepeak language as specified above ) addWordToSentence(splitPoint + MAX_WORD_LENGTH - length