静かで孤独な日記

のんびりたまに

POJ-3280

  • problem

3280 -- Cheapest Palindrome

  • code
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);

int dp[2001][2001];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
    cout<<fixed;
    int n,m;	
    cin>>n>>m;
	string s;cin>>s;
	int cost[30];
	for(int i=0;i<n;i++){
		char a;
		int b,c;
		cin>>a>>b>>c;
		cost[a-'a']=min(b,c);
	}
	//for(int i=0;i<m;i++)for(int j=0;j<m;j++)dp[i][j]=inf;
	//for(int i=0;i<m-1;i++){
	//	dp[i][i]=0;
	//	dp[i][i+1]=0;
	//}
	for(int i=m-1;i>=0;i--){
		for(int j=i+1;j<m;j++){
			dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'],dp[i][j-1]+cost[s[j]-'a']);
			if(s[i]==s[j]){
				dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
			}
		}
	}
	cout<<dp[0][m-1]<<endl;
    return 0;
}
  • 感想

正直よく分かってない。
典型らしいから、わからなきゃダメなんだろうけど。。
どうしてそういう考え方できるの?みたいな。
言ってることは分かるけど何か腑に落ちない。