POJ 3280 Cheapest Palindrome DP

題意:文字列を指定し、文字列に調整します.任意の文字を追加または削除できますが、1つの文字を追加または削除するたびに、最小のコストを求めるシナリオがあります.問題解:追加と削除の操作は同じなので、その文字を操作する代価として、追加と削除の小さな値しか要求されません.

#include <iostream>
using namespace std;

int dp[2001][2001], cost[30];
char s[2005];

int min ( int a, int b )
{
	return a < b ? a : b;
}

int main()
{
	char ch;
	int n, m, add, del, i, j;
	//freopen("a.txt","r",stdin);
	scanf("%d %d",&n,&m);
	scanf("%s",s+1);
	for ( i = 1; i <= n; i++ )
	{
		getchar();
		scanf("%c%d%d",&ch,&add,&del);
		cost[ch-'a'] = min ( add, del );
	}

	for ( i = m - 1; i >= 1; i-- )
	{
		for ( j = i + 1; j <= m; j++ )
		{
			if ( s[i] == s[j] )
				dp[i][j] = dp[i+1][j-1];
			else
				dp[i][j] =  min ( dp[i+1][j] + cost[s[i]-'a'], dp[i][j-1] + cost[s[j]-'a'] );	
		}
	}
	printf("%d
", dp[1][m] );
	return 0;
}


	

方法2:

#include <iostream>
using namespace std;

int dp[2001][2001], cost[30];
char s1[2005], s2[2005];

int min ( int a, int b )
{
	return a < b ? a : b;
}

int main()
{
	char ch;
	int n, m, add, del, i, j;
	scanf("%d %d",&n,&m);
	scanf("%s",s1+1);
	for ( i = 1; i <= n; i++ )
	{
		getchar();
		scanf("%c%d%d",&ch,&add,&del);
		cost[ch-'a'] = min ( add, del );
	}

	i = 1; j = m;
	while ( i <= m && j >= 1 )
	{
		s2[i] = s1[j];
		i++; j--;
	}

	dp[0][0] = 0;
	for ( i = 1; i <= m; i++ )
	{
		dp[i][0] = dp[i-1][0] + cost[s1[i]-'a'];
		dp[0][i] = dp[0][i-1] + cost[s2[i]-'a'];
	}

	for ( i = 1; i <= m; i++ )
	{
		for ( j = 1; j <= m; j++ )
		{
			if ( s1[i] == s2[j] )
				dp[i][j] = dp[i-1][j-1];
			else
				dp[i][j] =  min ( dp[i-1][j] + cost[s1[i]-'a'], dp[i][j-1] + cost[s2[j]-'a'] );	
		}
	}
	printf("%d
", dp[m][m] / 2 );
	return 0;
}