SRM 509 Div1 Med Palindromization

問題概要

回文をつくろう

3280 -- Cheapest Palindromeに文字をchangeする操作が加わっている。
基本的にはその問題と同じように区間DPをする。
ただしchangeが加わっているため、changeしてからerase,みたいなことができる。
まずchange操作はワーシャルフロイドしておく。
eraseは、changeしてからeraseする時のコストの最小値に更新する。一度の更新ではchangeした後のeraseの更新がまだ終わっていない可能性があるのでベルマンフォードっぽく頂点数(アルファベット数)回す。

#include <cstring>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
#define INF 10000000
class PalindromizationDiv1
{
	public:
	int add[30];
	int erase[30];
	int change[30][30];
	int dp[55][55];
	string Word;
	int rec(int l,int r)
	{
		if(l>=r)return 0;
		if(dp[l][r]!=-1)return dp[l][r];
		if(Word[l]==Word[r])return dp[l][r]=rec(l+1,r-1);
		int res=INF;
		int L = Word[l]-'a',R = Word[r]-'a';
		if(add[R]!=-1)res = min(res,rec(l,r-1)+add[R]);
		if(add[L]!=-1)res = min(res,rec(l+1,r)+add[L]);
		if(erase[R]!=-1)res = min(res,rec(l,r-1)+erase[R]);
		if(erase[L]!=-1)res = min(res,rec(l+1,r)+erase[L]);
		if(change[R][L]!=-1)res = min(res,rec(l+1,r-1)+change[R][L]);
		if(change[L][R]!=-1)res = min(res,rec(l+1,r-1)+change[L][R]);
		return dp[l][r]=res;
	}
	int getMinimumCost(string word, vector <string> operations)
	{
		Word = word;
		for(int i=0;i<30;i++)for(int j=0;j<30;j++)change[i][j]=INF;
		for(int i=0;i<30;i++)change[i][i]=0;
		for(int i=0;i<30;i++)add[i]=INF;
		for(int i=0;i<30;i++)erase[i]=INF;
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<operations.size();i++)
		{
			stringstream ss;
			ss << operations[i];
			string op;
			ss >> op;
			string a,b;
			int cost;
			if(op=="add")
			{
				ss >> a >> cost;
				add[a[0]-'a']=cost;
			}
			else if(op=="erase")
			{
				ss >> a >> cost;
				erase[a[0]-'a']=cost;
			}
			else
			{
				ss >> a >> b >> cost;
				change[a[0]-'a'][b[0]-'a']=cost;
			}
		}
		for(int k=0;k<30;k++)for(int i=0;i<30;i++)for(int j=0;j<30;j++)change[i][j]=min(change[i][j],change[i][k]+change[k][j]);
		for(int k=0;k<30;k++)
		{
			for(int i=0;i<30;i++)
			{
				for(int j=0;j<30;j++)
				{
					if(change[i][j]!=INF&&erase[j]!=INF)
					{
						erase[i]=min(erase[i],change[i][j]+erase[j]);
					}
				}
			}
		}
		int ans = rec(0,(int)word.size()-1);
		if(ans>=INF)return -1;
		else return ans;
	}
};