首页 > itarticle > [hihocoder

[hihocoder

admin 11月 14, 2020 0

链接

(text{hihoCoder - 1323})

题意

给定一个字符串(text S) ，最少需要几次增删改操作可以把(text S)变成一个回文字符串？一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符。输出最少的操作次数。

数据范围：字符串(text S)。(text S)的长度不超过(100), 只包含(text{A-Z})。

分析

这是一道区间(dp)的题目；也是经典的最少操作次数变成回文串的问题；对于

(dp[i][j])表示([i,j])区间的子串变成回文串最少操作次数，对于一个串(bab)，我们已经知道区间长度为(2)的所有状态，对于区间长度为(3)的阶段，此时(s[i]==s[j])，那么显然有(dp[i][j]=dp[i+1][j-1])，对于一个串(bba)，此时(s[i]!=s[j])，此时来说，我们只需要修改(s[i])为(s[j])或者修改(s[j])为(s[i])即可，所以我们有(dp[i][j]=min{dp[i+1][j]+1,dp[i][j-1]+1})。

初始状态(dp[i][i]=0)。

代码


#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int () {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

namespace segment_Tree {
	struct Tree {
		int l, r, max;
	} tree[4 * MAXN];

	inline void push_up(int x) {
		tree[x].max = max(tree[x << 1].max, tree[x << 1 | 1].max);
	}

	inline void build(int x, int l, int r) {
		tree[x].l = l, tree[x].r = r;
		if (l == r) {
			tree[x].max = 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(x << 1, l, mid);
		build(x << 1 | 1, mid + 1, r);
		push_up(x);
	}

	inline void update(int x, int pos, int val) {
		int l = tree[x].l, r = tree[x].r;
		if (l == r) {
			tree[x].max = max(tree[x].max, val);
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid)update(x << 1, pos, val);
		else update(x << 1 | 1, pos, val);
		push_up(x);
	}

	inline int query(int x, int l, int r) {
		int le = tree[x].l, ri = tree[x].r;
		if (l <= le && ri <= r) {
			return tree[x].max;
		}
		int mid = (le + ri) >> 1;
		int maxm = 0;
		if (l <= mid) maxm = max(maxm, query(x << 1, l, r));
		if (r > mid) maxm = max(maxm, query(x << 1 | 1, l, r));
		return maxm;
	}
}

int t, n, m, a[10005], dp[10009][509];
string s;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			dp[i][j] = dp[i - 1][j - 1] + a[i];
		dp[i][0] = dp[i - 1][0];
		for (int j = 1; j <= i && j <= m; j++)
			dp[i][0] = max(dp[i][0], dp[i - j][j]);
	}
	cout << dp[n][0] << endl;
}