Решение задачи Сложная загадка с Codeforces

Без пояснения   Просмотров: 65

Василий очень любит разные загадки. Сегодня он нашёл загадку, которую не смог решить сам, поэтому он просит вас помочь ему.

У Василия есть n строк, состоящих из строчных букв английского алфавита. Он хочет, чтобы строки располагались в лексикографическом порядке (как в словаре), но при этом не хочет менять их местами. Единственное, что Василий может делать, это разворачивать строки (первая буква становится последней, вторая предпоследней и так далее).

Чтобы развернуть i-ю строку Василию, надо потратить c i единиц энергии. Василия интересует минимальное количество энергии, которое необходимо потратить, чтобы строки шли в лексикографическом порядке.

Строка A лексикографически меньше строки B, если она короче B (|A| < |B|) и является её префиксом, либо ни одна из них не является префиксом другой, и в первой позиции, где они различаются, в строке A стоит символ с меньшим номером.

В данной задаче две одинаковые строки на соседних позициях не нарушают порядок лексикографической сортировки.

Код 

#include <bits/stdc++.h>
using namespace std;
#define N 100001
string s[N][2];
long long dp[N][2];
int n,c[N],i,j,k;
int main(){
	scanf("%d",&n);
	for(i = 1; i <= n; i++)
        scanf("%d",&c[i]);
	for(i = 1; i <= n; i++){
		cin >> s[i][0];
		s[i][1] = s[i][0];
		reverse(s[i][1].begin(),s[i][1].end());
		for(j = 0; j < 2; j++){
			dp[i][j] = 1e18;
			for(k = 0; k < 2; k++)
				if(s[i][j] >= s[i - 1][k])
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * c[i]);
		}
	}
	long long ans = min(dp[n][0],dp[n][1]);
	printf("%lld\n", ans >= 1e18?-1:ans);
	return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта