贪心大法90分求助!
查看原帖
贪心大法90分求助!
409860
yu1102楼主2022/8/1 18:31
#include <bits/stdc++.h>
using namespace std;

int line, k, n, m, sum[300], ans, sepa[300];
string s, a[10];

struct node
{
	int sum, id;
	bool operator < (const node &r) const
	{
		if (sum != r.sum) return sum < r.sum;
		return id < r.id;
	}
} p[300];

bool cmp(string s1, string s2)
{
	return s1.size() < s2.size();
}

void read()
{
	cin >> line >> k;
	n = line * 20;

	string s2;
	for (int x = 1; x <= line; x++) cin >> s2, s += s2;
	
	cin >> m;
	for (int x = 1; x <= m; x++)
		cin >> a[x];	
}

int main()
{
	read();
	sort(a + 1, a + 1 + m, cmp);
	
	while (--k)
	{
//		for (int x = 0; x < n; x++)
//			cout << sepa[x] << ' ';
//		cout << endl;
		for (int x = 0; x < n; x++)
			p[x].id = x, p[x].sum = 0;
		ans = 0;
		for (int x = 0; x < n; x++)
		{
			for (int y = 1; y <= m; y++)
				if (x + a[y].size() <= n && s.substr(x, a[y].size()) == a[y])
				{
					bool ok = 1;
					for (int z = x + 1; z < x + a[y].size(); z++)
						if (sepa[z]) ok = 0;
					if (ok)
					{
						ans++;
						for (int z = x + 1; z < x + a[y].size(); z++)
							p[z].sum ++;					
					}
					break;
				}
		}
		for (int x = 0; x < n; x++)
			if (sepa[x]) p[x].sum = INT_MAX;
		sort(p + 1, p + n);
		ans -= p[1].sum;
		sepa[p[1].id] = 1;
	}
	
	cout << ans << endl;
} 
2022/8/1 18:31
加载中...