dp--B - Hard problem

B - Hard problem

Vasiliy is fond of solving different tasks. Today he found one he wasn't able to solve himself, so he asks you to help.

Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the i-th string Vasiliy has to spent c_i units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.

String A is lexicographically smaller than string B if it is shorter than B (|A| < |B|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in A is smaller than the character in B.

For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers c_i (0 ≤ c_i ≤ 10⁹), the i-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the i-th string.

Then follow n lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn't exceed 100 000.

Output

If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print - 1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.

　　题目大意：给定你n个字符串，以及每条字符串变动所需的代价ci。问，能否通过只对某个或某些字符串进行翻转（即头尾调换，abcde->edcba），使这n条字符串为字典序排序（短的在前，小的在前）

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 const int maxn = ;

 const LL INF=1e15;

 int c[maxn];

 string str[maxn][];

 LL dp[maxn][];

 string reverse(string s){//翻转

     string res=s;

     int i, len=res.length();

     for(i=;i<len/;++i)

         swap(res[i], res[len--i]);

     return res;

 }

 int main(){

     int n, i;

     scanf("%d",&n);

         for(i=;i<n;++i)

             scanf("%d",&c[i]);

         for(i=;i<n;++i){

             cin>>str[i][];

             str[i][]=reverse(str[i][]);//翻转

         }

         for(i=;i<n;++i)//初始化

             dp[i][]=dp[i][]=INF;

         dp[][]=; dp[][]=c[];

         for(i=;i<n;++i){

             if(str[i][]>=str[i-][])//原str i 大于 原str i-1

                 dp[i][]=dp[i-][];

             if(str[i][]>=str[i-][])//翻转str i 大于 原str i-1

                 dp[i][]=dp[i-][]+c[i];

             if(str[i][]>=str[i-][])//原str i 大于 翻转str i-1

                 dp[i][]=min(dp[i][],dp[i-][]);

             if(str[i][]>=str[i-][])//翻转str i 大于 翻转str i-1

                 dp[i][]=min(dp[i][],dp[i-][]+c[i]);

             if(dp[i][]==INF&&dp[i][]==INF)

                 break;

         }

         if(i==n)

             printf("%I64d\n",min(dp[n-][],dp[n-][]));

         else

             printf("-1\n");

     return ;

 }

　　这是今天训练的B题，但是我却放到了后面才做，因为我看不懂题意（即使是借助了翻译软件），最后去翻了外面的博客才读懂题意，所以读懂题意是解决问题的第一条件。

　　代价ci，即使告诉我这是dp专题，我却怎么都没办法联系起来，一开始我甚至觉得ci是无关紧要的；但是当我们把ci和对相邻字符串的字典序的判断联系在一起时，这个题目就非常好做了。我们只要把dpi的初始值设置的非常大或者非常小，在循环中做判断时，如果通过所谓的字符翻转，能够实现字符串的字典序排序，我就将dpi的值改为ci（以便最后求出总的代价）；如果不能实现字典序排序，那就不改变dpi的值，最后结束时只要判断dpi是否为初始设置的极端值，就能判断所有的字符串是否能按字典序排序。

　　借助的dp数组，要巧妙的和需要求的值联系起来，既能作判断，又能求结果。

巴特西

dp--B - Hard problem

B - Hard problem

最新文章

热门文章