洛谷 P1026 统计单词个数（分组+子串预处理）（分组型dp再次总结）

一看完这道题就知道是划分型dp

有两个点要注意

（1）怎么预处理子串。

$sum[i][j] = sum[i+1][j] + judge(i, j)$

$judge(i, j)$ 表示以i为开头，结尾在j之前（含），有没有子串，有就1，没有就0

（2）dp的过程

这种分成k组最优的题目已经高度模板化了，我总结一下吧

//f[i][j]表示把前j个数分成i组的最优价值

memset(f, 0xc0, sizeof(f)); //初始化

f[0][0] = 0;       //不要忘记了

_for(k, 1, K)      //枚举组数

	_for(i, 1, len) //前i个字符

		_for(j, 1, i) //断点

			f[k][i] = max(f[k][i], f[k-1][j-1] + sum[j][i]); //字母不要写错

printf("%d\n", f[K][len]);

最后用string可以很方便的连接字符串，直接+=

char的话用strcat, stract(a, b)表示把b连到a后面

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<iostream>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 212;

string s, t, word[10];

int p, K, n, sum[MAXN][MAXN], f[MAXN][MAXN];

bool judge(int i, int j)

{

	REP(r, 0, n)

	{

		int len = word[r].length();

		if(len > (j - i + 1)) continue;

		REP(k, 0, len)

		{

			if(word[r][k] != s[i+k]) break;

			if(k == len - 1) return true;

		}

	}

	return false;

}

int main()

{

	while(~scanf("%d%d", &p, &K))

	{

		s = "0";

		REP(i, 0, p)

		{

			cin >> t;

			s += t;

		}

		p *= 20;

		scanf("%d", &n);

		REP(i, 0, n) cin >> word[i];

		memset(sum, 0, sizeof(sum));

		_for(j, 1, p)

			for(int i = j; i >= 1; i--)

				sum[i][j] = sum[i+1][j] + judge(i, j);

		memset(f, 0xc0, sizeof(f));

		f[0][0] = 0;

		_for(k, 1, K)

			_for(i, 1, p)

				_for(r, 1, i)

					f[k][i] = max(f[k][i], f[k-1][r-1] + sum[j][i]);

		printf("%d\n", f[K][p]);

	}

	return 0;

}

巴特西

洛谷 P1026 统计单词个数（分组+子串预处理）（分组型dp再次总结）

最新文章

热门文章

巴特西

洛谷 P1026 统计单词个数 （分组+子串预处理）（分组型dp再次总结）

最新文章

热门文章

洛谷 P1026 统计单词个数（分组+子串预处理）（分组型dp再次总结）