字数

750 字

阅读时间

4 分钟

马拉车

P3805 模板manacher 算法

1、写出暴力方法

• 先处理字符串，用#分隔，头为都要有

• 用一个r数组存储每个点的最长子串的半径

• 枚举每个点然后向外扩张

• 扩张完毕后自减 表示半径

• 获取最大值

暴力法如下:

string deal(string& str) {
    string temp = "#";
    for (char ch : str)(temp += ch) += '#';
    return temp;
}
int r[22000010] = { 0 };
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string str;
    cin >> str;
    str = deal(str);
    int len = str.length(), ans = 0, c = 0;
    for (int i = 0; i < len; i++) {
        while (i - r[i] >= 0 && str[i - r[i]] == str[i + r[i]])r[i]++;
        r[i]--;
        ans = max(ans, r[i]);
    }
    return 0;
}

2、通过利用对称性

• 解释：在一个较大的半径范围内 其中的数如果半径较小，那么关于大半径范围对称
• 如图所示

• 用一个变量c记录当前范围最大的并且范围最靠右端的位置
• 每次遇到新的位置时
  • 先将新位置的半径赋为对称的对应半径
    • 如果出现半径超出范围，如图中倒数第二个C，那么赋值为到最右边半径的距离
  • 然后向外拓展判断
  • 最后比较c和当前index的最右端

string deal(string& str) {
    string temp = "#";
    for (char ch : str)(temp += ch) += '#';
    return temp;
}
int r[22000010] = { 0 };
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string str;
    cin >> str;
    str = deal(str);
    int len = str.length(), ans = 0, c = 0;
    //由于下标0位置为'#'所以直接从下标1开始
    for (int i = 1; i < len; i++) {
        //如果当前点在c的包裹内就赋值，如果刚好在c半径的右边一位，会出现-1
        if (c + r[c] >= i)r[i] = min(r[2 * c - i], c + r[c] - i);
        //暴力法
        while (i - r[i] >= 0 && str[i - r[i]] == str[i + r[i]])r[i]++;
        r[i]--;
        //如果最右端更新，那么c也更新
        if (c + r[c] < i + r[i])c = i;
        ans = max(ans, r[i]);
    }
    cout << ans;
    return 0;
}

动态规划

区间动态规划

石子问题

#include<iostream>
using namespace std;
#include<cstring>
const int maxn = 305;

int main()
{
	int a[maxn];
	long long dp[maxn][maxn];
	int sum[maxn];
	int N;
	cin >> N;
	memset(a, 0, sizeof(a));
	memset(dp, 0, sizeof(dp));
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= N; i++)
	{
		cin >> a[i];
		//通过前缀和数组记录合成一堆时的得分
		sum[i] = a[i] + sum[i - 1];
	}

	//区间长度len,从2开始
	for (int len = 2; len <= N; len++)
	{
		//起始位置，从1开始，到N-len+1结束
		for (int i = 1; i <= N - len + 1; i++)
		{
			//根据区间长度和开始位置确定j
			int j = i + len - 1;
			//由于要的是最小值，先设置一个较大值
			dp[i][j] = 3000000;
			//将i到j区间分隔为  i到k和k+1到j两个区间
			for (int k = i; k < j; k++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
		}
	}
	//最后输出1到N区间的最大值，即dp[1][N]
	cout << dp[1][N] << endl;
	return 0;
}

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

65bbf-update 算法学习 and modify 算法题解