[NOI2020]古城之谜

原题目太复杂了。

放个链接

通俗的说一下题目

• 句子 = 名词短语(+动词短语+名词短语+动词短语+...)
• 动词短语 = (辅词+辅词+辅词+...+)动词
• 名词短语 = (辅词+辅词+辅词+...+)名词

给你一个文章，问怎么分可以把句子数量最少的情况下，单词数量也最少。

询问这个两者的次数，保证存在一种合法的划分方式。单词长度不超过 20

，

解题思路

一看就是个 dp。考虑令 为做到 位置之后结尾的次的情况。

显然我们如果不考虑辅词的话，只需要两种情况

• 0 表示以名词结束
• 1 表示以动词结束

很明显我们的一个状态是 pair 的。

但是这样子明显无法判断辅词的时候，考虑设记四种状态。

• v. end
• n.end
• n. + a. + a. + ...
• n. + v. + v. + ...

分别用四个状态来代表

转移方程与上边类似，就不说了。

同时，在判断两个字符串是否一样的时候，可以用Trie优化。

#include <bits/stdc++.h>
using std::min;
using std::cin;
using std::cout;
using std::max;
using std::pair;
using std::string;
using std::make_pair;
const int N = 1001, INF = 0x3f3f3f3f;
#define For( i, j, k ) for( int i = j; i <= k; ++i )
char s[ N ], T[ N * 5 ];
pair < int, int > f[ N * 5 ][ 4 ];
class Trie
{
 int cnt, rt;
 struct Node
 {
  int son[ 26 ];
  bool tag[ 3 ];
 }elvahs[ N * 30 ];
public:
 void Insert( char* s, int v )
 {
  int u = rt;
  for( ; *s; ++s )
  {
   if( !elvahs[ u ].son[ *s - 'a' ] )
    elvahs[ u ].son[ *s - 'a' ] = ++cnt;
   u = elvahs[ u ].son[ *s - 'a' ];
  }
  elvahs[ u ].tag[ v ] = 1;
  return;
 }
 bool* Query( char* s, int len )
 {
  int u = rt;
  for( ; len; --len, ++s )
  {
   if( !elvahs[ u ].son[ *s - 'a' ] )
    return elvahs[ 0 ].tag;
   u = elvahs[ u ].son[ *s - 'a' ];
  }
  return elvahs[ u ].tag;
 }
 Trie( )
 {
  cnt = rt = 1;
 }
}zhltao;
int main( )
{
 int n;
 std::ios::sync_with_stdio( false );
 cin >> n;
 For( i, 1, n )
 {
  cin >> s;
  if( s[ 0 ] == 'n' )
   zhltao.Insert( s + 2, 0 );
  else if( s[ 0 ] == 'v' )
   zhltao.Insert( s + 2, 1 );
  else
   zhltao.Insert( s + 2, 2 );
 }
 cin >> T + 1;
 int L = strlen( T + 1 ) - 1;
 bool *B;
 memset( f, 63, sizeof f );
 f[ 0 ][ 0 ] = std::make_pair( 0, 0 );
 For( i, 1, L )
 {
  for( int j = i - 1; j >= std::max( 0, i - 20 ); --j )
  {
   B = zhltao.Query( T + j + 1, i - j );
   pair < int, int > lo = min( f[ j ][ 0 ], f[ j ][ 2 ] ) , li = min( f[ j ][ 1 ], f[ j ][ 3 ] );
   if( B[ 0 ] )
   {
    f[ i ][ 0 ] = min( f[ i ][ 0 ], make_pair( lo.first + 1, lo.second + 1 ) );
    f[ i ][ 0 ] = min( f[ i ][ 0 ], make_pair( li.first, li.second + 1 ) ); 
   }
   if( B[ 1 ] && j != 0 )
    f[ i ][ 1 ] = min( f[ i ][ 1 ], make_pair( lo.first, lo.second + 1 ) );
   if( B[ 2 ] )
   {
    f[ i ][ 2 ] = min( f[ i ][ 2 ], make_pair( lo.first, lo.second + 1 ) );
    f[ i ][ 3 ] = min( f[ i ][ 3 ], make_pair( li.first, li.second + 1 ) ); 
   }
  }
 }
 pair < int, int > res = std::min( f[ L ][ 0 ], f[ L ][ 1 ] );
 cout << res.first << '\n' << res.second;
 return 0;
}