USACO2007OPEN GOLD 廉价回文

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Sep 05 00:52:32 CST 2018

In Category: NoCategory

Description：

给出每个字符添加和删除的代价，用最小的代价使得原串变成了一个回文串。

$1\le n \le 2000$

Solution：

发现添加和删除在意义上是等价的，于是把两个代价取个 $min$ 只考虑删除，然后区间 $DP$ ，如果区间左右相同那么就不用付出代价，否则付出左边或右边的代价。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2010

inline int getc()

{

	register char c = getchar();

	while(!islower(c))c = getchar();

	return c - 'a';

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int a[MAXN];

int val[27];

int f[MAXN][MAXN];

int main()

{

	scanf("%d%d",&m,&n);

	for(int i = 1;i <= n;++i)a[i] = getc();

	for(int i = 1;i <= m;++i)val[getc()] = min(read(),read());

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

	for(int i = 1;i <= n;++i)f[i][i] = 0;

	for(int i = 1;i < n;++i)f[i + 1][i] = 0;

	for(int l = 2;l <= n;++l)

	{

		for(int i = 1;i <= n - l + 1;++i)

		{

			int j = i + l - 1;

			if(a[i] == a[j])f[i][j] = f[i + 1][j - 1];

			f[i][j] = min(f[i][j],min(f[i + 1][j] + val[a[i]],f[i][j - 1] + val[a[j]]));

		}

	}

	cout << f[1][n] << endl;

	return 0;

}

In tag: DP-区间DP

wjh15101051