PoskeVH
Lv.1
喜欢你
获赞:5151收藏:3447浏览:121973作品收藏:1181
签名:域名转让ofan.cn 有意者联系 小号：_Creat
Lv.1
喜欢你
签名:域名转让ofan.cn 有意者联系 小号：_Creat
在 【C++】这题咋做 中回复
？？？
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int p, k, s, n, len[205], num[205][205], f[205][45];
string str = " ", t, w[10];
bool isWordInStr(const string& s, const string& word, int start)
{
for (int i = 0; i < word.length(); i++)
{
if (s[start + i]!= word[i])
{
return false;
}
}
return true;
}
void countWords(int start)
{
int end = min(start + 10, n + 1);
for (int i = start; i < end; i++)
{
len[i] = 0;
for (int j = 0; j < s; j++)
{
if (isWordInStr(str, w[j], i))
{
len[i]++;
}
}
}
}
int dp(int i, int j)
{
if (f[i][j]!= -1)
{
return f[i][j];
}
if (j == 0)
{
f[i][j] = 0;
return 0;
}
if (i == 0)
{
f[i][j] = 0;
return 0;
}
int res = 0;
for (int l = 0; l < i; l++)
{
int temp = dp(l, j - 1) + num[l + 1][i];
if (temp > res)
{
res = temp;
}
}
f[i][j] = res;
return res;
}
int main()
{
cin >> p >> k;
for (int i = 1; i <= p; i++)
{
cin >> t;
str += t;
}
n = p * 20;
cin >> s;
memset(len, 0x3f, sizeof(len));
memset(f, -1, sizeof(f));
for (int i = 0; i < s; i++)
{
cin >> w[i];
}
for (int i = 1; i <= n; i++)
{
countWords(i);
}
for (int i = 1; i <= n; i++)
{
num[i][i] = len[i];
for (int j = i + 1; j <= n; j++)
{
num[i][j] = num[i][j - 1] + len[j];
}
}
int ans = dp(n, k);
cout << ans << endl;
return 0;
}
2024-08-04T14:00:37 点赞:0