2071. Juice Cocktails
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Once n Denchiks come to the bar and each orders a juice cocktail. It could be from 1 to 3 different juices in each cocktail. There are three juices in the bar: apple, banana and pineapple juice.
Every Denchik has his favourite juice cocktail. The cocktail is uniquely defined by those kinds of juices which it contains. Of course, each Denchik ordered his favorite cocktail. The barman can put all n glasses in a long row and pour the juice in the segment of successive glasses.
The bar is very popular, so the barman wants to serve Denchiks as quickly as possible. So, he wants to arrange glasses in a certain way to minimize the amount of "pourings." For one "pouring" he can pour one kind of juice in one segment of successive glasses.
As it is known, apple juice has higher density than banana juice. And density of banana juice is higher than that of pineapple one. Therefore, not to mix juices in a cocktail, you should firstly pour the apple, then banana and finally pineapple juice.
Of course, you must pour only that juices into each glass which are parts of a certain cocktail, but the relative order of juices should remain unchanged. There‘re too many Denchiks, so the barman can‘t understand how should he arrange glassess. Could you?
Input
The first line contains integer n (1 ≤ n ≤ 105).
Next n lines describe Denchiks‘orders. Each order is described by one line, which consists of from 1 to 3 title Latin letters — A, B, P. The i-th line gives the kinds of juice included in the i-th order (A = Apple, B = Banana, P = Pineapple). The letters inside the string are arranged in this only order — "ABP", so to make the string you should eliminate some letters (perhaps, none) from "ABP" combination.
Output
In the first line print the minimal number of "pourings."
In the second line output the indices of glasses in order in which they have to be arranged in row. Assume that the orders and corresponding glasses are numbered from 1 to n in the input order.
If there are several optimal ways of glasses arrangement, output any of them.
Sample
| input | output |
|---|---|
3 |
3 |
Problem Author: Mikhail Rubinchik (prepared by Nickolai Permyakov, Alexey Danilyuk)
Problem Source: Ural Regional School Programming Contest 2015
Problem Source: Ural Regional School Programming Contest 2015
Tags: none (hide tags for unsolved problems)
Difficulty: 428
题意：给出n个串，只由A、B、P三个字母组成，且顺序是ABP，即它们的相对顺序就是ABP
每次可以消去连续一些串的相同的首字母，比如
ab -> b
ap p
问在最开始自有安排它们顺序后，最少多少次可以消去全部，输出方案
分析：
首先相同构成的肯定放在一起
一共只有7种串，暴力枚举他们的排列，然后暴力贪心的消去
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define INF (1000000001)
#define sz(x) ((int) (x).size())
#define pub push_back const int N = ;
const string STORE[] = {"A", "AB", "B", "BP", "ABP", "AP", "P"};
int n, m;
string data[N];
vector<int> cnt[];
int arr[N], it[N], pos[];
string origin[], tmp[];
int ansPos[]; inline void input()
{
cin >> n;
for(int i = ; i < n; i++) cin >> data[i];
} inline int work()
{
char ch[] = {'A', 'B', 'P'};
int it[] = {}, ret = ;
for(int t = ; t < ; t++)
for(int i = ; i < m; i++)
if(tmp[i][it[i]] == ch[t])
{
it[i]++;
int j = i;
while(j + < m)
{
if(it[j + ] >= sz(tmp[j + ])) break;
if(tmp[j + ][it[j + ]] != ch[t]) break;
j++;
it[j]++;
}
ret++;
i = j;
}
return ret;
} inline int num(string &str)
{
int x;
if(str == "A") x = ;
else if(str == "AB") x = ;
else if(str == "B") x = ;
else if(str == "BP") x = ;
else if(str == "ABP") x = ;
else if(str == "AP") x = ;
else if(str == "P") x = ;
return x;
} inline bool cmp(string a, string b)
{
int x = num(a), y = num(b);
return x < y;
} inline void solve()
{
for(int i = ; i < n; i++)
if(data[i] == "A") cnt[].pub(i);
else if(data[i] == "AB") cnt[].pub(i);
else if(data[i] == "B") cnt[].pub(i);
else if(data[i] == "BP") cnt[].pub(i);
else if(data[i] == "ABP") cnt[].pub(i);
else if(data[i] == "AP") cnt[].pub(i);
else if(data[i] == "P") cnt[].pub(i); m = ;
for(int i = ; i < ; i++)
if(sz(cnt[i]))
{
pos[m] = i;
m++;
}
int ans = INF;
do
{
for(int i = ; i < m; i++) tmp[i] = STORE[pos[i]];
int o = work();
if(ans > o)
{
ans = o;
for(int i = ; i < m; i++) ansPos[i] = pos[i];
}
} while(next_permutation(pos, pos + m)); int out = ;
printf("%d\n", ans);
for(int i = ; i < m; i++)
for(int j = ; j < sz(cnt[ansPos[i]]); j++)
{
out++;
if(out == n) printf("%d\n", cnt[ansPos[i]][j] + );
else printf("%d ", cnt[ansPos[i]][j] + );
}
} int main()
{
ios::sync_with_stdio();
input();
solve();
return ;
}