POJ-3280
- problem
- 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; }
- 感想
正直よく分かってない。
典型らしいから、わからなきゃダメなんだろうけど。。
どうしてそういう考え方できるの?みたいな。
言ってることは分かるけど何か腑に落ちない。