划分型动态规划之 CODE[VS] 1040 统计单词个数 2001年NOIP全国联赛提高组-白红宇

划分型动态规划之 CODE[VS] 1040 统计单词个数 2001年NOIP全国联赛提高组

阅读量：5280 次

发布时间：2019-06-14

本文共 2903 字，大约阅读时间需要 9 分钟。

/*dp[i][k] := 前i+1个字符组成的字符串，划分为k份，每份中包含的单词个数加起来总数的最大值。 初始化：	dp[][] = -0x3f3f3f3f          // 注意：对于dp[i][k]，若(i+1)
    
     = strArr[m].size()		      2）此字符串首字符的位置fst在求val[i][j-1]和求num(j)时，没有用过			  对应代码：!used[j - strArr[m].size() + 1]			3）strS[i,j] == strArr[m]			  对应代码：strSource.substr(j - strArr[m].size() + 1, strArr[m].size()) == strArr[m]		     则：+1		     最后找到几个满足这三个条件的首位置fst，num(j)的值就是几。				*/

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 using namespace std; 13 const int INF = -0x3f3f3f3f; 14 const int MaxN = 210; 15 const int MaxK = 50; 16 17 int dp[MaxN][MaxK]; 18 int val[MaxN][MaxN]; 19 int len, K, S; 20 string strSource; 21 string strArr[10]; 22 23 24 void iniVal() 25 { 26 bool used[MaxN]; 27 for (int i = 0; i < len; ++i) 28 { 29 memset(used, 0, sizeof(used)); 30 for (int j = i; j < len; ++j) 31 { 32 if (i != j) val[i][j] = val[i][j - 1]; 33 for (int m = 0; m < S; ++m) 34 { 35 if ((j - i + 1 >= strArr[m].size()) && !used[j - strArr[m].size() + 1] 36 && (strSource.substr(j - strArr[m].size() + 1, strArr[m].size()) == strArr[m])) 37 { 38 ++val[i][j]; 39 used[j - strArr[m].size() + 1] = true; 40 } 41 } 42 } 43 } 44 } 45 46 void Solve() 47 { 48 for (int i = 0; i < len; ++i) 49 { 50 dp[i][1] = val[0][i]; 51 } 52 for (int i = 0; i < len; ++i) 53 { 54 for (int j = 0; j < i; ++j) 55 { 56 for (int k = 2; k <= K; ++k) 57 { 58 dp[i][k] = max(dp[i][k], dp[j][k - 1] + val[j+1][i]); 59 int bbb = 1; 60 } 61 } 62 } 63 cout << dp[len-1][K] << endl; 64 65 66 67 /*cout << "\n\n\n\n" << "val:----------------------------" << endl; 68 for (int i = 0; i < len; ++i) 69 { 70 for (int j = 0; j < len; ++j) 71 { 72 cout << val[i][j] << " "; 73 } 74 cout << endl; 75 } 76 77 cout << "\n\n\n\n" << "dp:----------------------------" << endl; 78 for (int i = 0; i < len; ++i) 79 { 80 for (int j = 1; j <= K; ++j) 81 { 82 cout << dp[i][j] << " "; 83 } 84 cout << endl; 85 }*/ 86 } 87 88 int main() 89 { 90 #ifdef HOME 91 freopen("in", "r", stdin); 92 //freopen("out", "w", stdout); 93 #endif 94 95 int cas; 96 cin >> cas; 97 while (cas--) 98 { 99 strSource = "";100 memset(val, 0, sizeof(val));101 for (int i = 0; i < MaxN; ++i)102 {103 for (int j = 0; j < MaxK; ++j)104 {105 dp[i][j] = INF;106 }107 }108 int p;109 cin >> p >> K;110 string strTmp;111 for (int i = 0; i < p; ++i)112 {113 cin >> strTmp;114 strSource += strTmp;115 }116 len = strSource.size();117 cin >> S;118 for (int i = 0; i < S; ++i)119 {120 cin >> strArr[i];121 }122 iniVal();123 Solve();124 }125 126 #ifdef HOME127 cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;128 _CrtDumpMemoryLeaks();129 system("pause");130 #endif131 return 0;132 }