POJ 3280 Cheapest Palindrome(区间dp)

此题为取两端的区间dp。

分情况讨论：

• 1. a i = a j a_i=a_j ai​=aj​， d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] dp[i][j]=dp[i+1][j-1] dp[i][j]=dp[i+1][j−1]
• 否则，分四种情况，删左边，删右边，左边加 s [ j ] s[j] s[j]，右边加 s [ i ] s[i] s[i]。

时间复杂度： O ( n 2 ) O(n^2) O(n2)

code

// Problem: Cheapest Palindrome
// Contest: Virtual Judge - POJ
// URL: https://vjudge.net/problem/POJ-3280#author=AlexPanda
// Memory Limit: 65 MB
// Time Limit: 2000 ms
// Date: 2021-05-22 10:36:05
// --------by Herio--------

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=2e3+100,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int add[300],del[300];
char a[N];
int n,m;
int f[N][N];
int main(){
	scanf("%d%d\n%s",&n,&m,a+1);
	for(int i=1;i<=n;i++){
		char ch;
		scanf("\n%c",&ch);
		scanf("%d%d",&add[ch],&del[ch]);
	}
	for(int l=2;l<=m;l++)
		for(int i=1,j=i+l-1;j<=m;i++,j++){
		if(a[i]==a[j]) f[i][j]=f[i+1][j-1];
		else f[i][j]=min(min(f[i+1][j]+del[a[i]],f[i][j-1]+del[a[j]]),min(f[i+1][j]+add[a[i]],f[i][j-1]+add[a[j]]));
	}
	printf("%d\n",f[1][m]);
	return 0;
}