Codeforces #367 Div.2 C. Hard problem
problem
問題要約
コスト
と
文字列
が与えられる。
をするために, コスト がかかる
うまいことをして, 文字列を辞書順に昇順()となるようにしたい.
昇順にできるとき, 最小の総コストを求めて, どう頑張ってもできない時は-1を出力する
解き方
dpを使う
: 番目の文字列までを昇順にするときに必要な最低のコスト
ここで, の時, n番目をひっくり返すときを意味し, の時, n番目をひっくり返さないことを意味する.
更新式は数式で表記すると面倒なので, ソースコード参照
事前処理として, を反転させた配列を用意しておく
注意事項
がやたらでかいので, オーバーフロー, infの定義に注意する
最終的な出力の最大値は,
SourceCode
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define linf 0x3f3f3f3f3f3f3f3f #define PB push_back #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define SET(a,c) memset(a,c,sizeof a) #define CLR(a) memset(a,0,sizeof a) #define pii pair<int,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define MIN(a,b) (a>b?b:a) #define MAX(a,b) (a>b?a:b) #define pi 2*acos(0.0) #define INFILE() freopen("in0.txt","r",stdin) #define OUTFILE()freopen("out0.txt","w",stdout) #define in scanf #define out printf #define ll long long #define ull unsigned long long #define eps 1e-14 #define FST first #define SEC second // n次元配列の初期化。第2引数の型のサイズごとに初期化していく。 template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } int main(void) { int N; cin >> N; vector<int> C(N); for(auto &a:C) cin >> a; vector<string> S(N); for(auto &a:S) cin >> a; vector<string> revS = S; REP(i,N) reverse(ALL(revS[i])); ll dp[100001][2] = {}; REP(i,100001) REP(j,2) dp[i][j] = (ll)(1e14); dp[0][0] = 0; dp[0][1] = C[0]; FOR(index, 0,N-1){ if(S[index] <= S[index+1]) dp[index+1][0] = min(dp[index+1][0], dp[index][0]); if(revS[index] <= S[index+1]) dp[index+1][0] = min(dp[index+1][0], dp[index][1]); if(S[index] <= revS[index+1]) dp[index+1][1] = min(dp[index+1][1], dp[index][0]+C[index+1]); if(revS[index] <= revS[index+1]) dp[index+1][1] = min(dp[index+1][1], dp[index][1]+C[index+1]); } ll res = min(dp[N-1][0], dp[N-1][1]); cout << (res>=1e14?-1:res) << endl; return 0; }