「CF83E」Two Subsequences
On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.
Let {a1, a2, …, an} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let’s define the compression function:
- f(empty sequence) = empty string
- f(s) = s.
- f(s1, s2) = the smallest in length string, which has one of the prefixes equal to s1 and one of the suffixes equal to s2. For example, f(001, 011) = 0011, f(111, 011) = 111011.
- f(a1, a2, …, an) = f(f(a1, a2, an - 1), an). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.
Valera faces a real challenge: he should divide the given sequence {a1, a2, …, an} into two subsequences{b1, b2, …, bk} and {c1, c2, …, cm}, m + k = n, so that the value of S = |f(b1, b2, …, bk)| + |f(c1, c2, …, cm)| took the minimum possible value. Here |p| denotes the length of the string p.
Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don’t have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).
Help Valera to find the minimum possible value of S.
The first line of input data contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The i + 1-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.
Print a single number — the minimum possible value of S.
|
1 2 3 4 |
3 01 10 01 |
|
1 |
4 |
|
1 2 3 4 5 |
4 000 111 110 001 |
|
1 |
8 |
|
1 2 3 4 5 6 |
5 10101 01010 11111 01000 10010 |
|
1 |
17 |
Detailed answers to the tests:
- The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
- The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
- The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 1
题解
xhr神犇的cf题目泛做中有详细题解，第42页
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define rad 100000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[25]; int n,L,delta; char a[200005][25]; int b[200005][25],S[200005]; int dp[25][1048576]; int F(int x,int y) { int t1=S[x],t2=S[y]; for(int i=L;i;i--) { if(t1==t2)return i; t2>>=1;t1-=b[x][L-i+1]*bin[i-1]; } return 0; } int main() { bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1; memset(dp,127/3,sizeof(dp)); n=read(); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); L=strlen(a[1]+1); for(int i=1;i<=n;i++) for(int j=1;j<=L;j++) { b[i][j]=a[i][j]-'0'; S[i]+=b[i][j]*bin[L-j]; } dp[0][0]=0;delta=L; for(int i=1;i<n;i++) { int tmp=L-F(i,i+1),mn=inf,now=0; delta+=tmp; for(int j=0;j<=L;j++) { now=(now<<1)+b[i+1][j]; mn=min(mn,dp[j][now]+L-j); } now=0; for(int j=0;j<=L;j++) { dp[j][now]=min(dp[j][now],mn-tmp); now+=b[i][L-j]*bin[j]; } } int ans=0; for(int i=0;i<=L;i++) for(int j=0;j<bin[i];j++) ans=min(ans,dp[i][j]); printf("%d\n",ans+delta); return 0; } |
OI 课件=>
clutch bottega veneta
Mas eu estava brincando com meu marido, e fazê-lo para ele, tanto do nosso deleite.
giuseppe zanotti design outlet neum¨¹nster
Supreme Post¡Tanks 4 sharing!
ray ban 3025 hangover
Super! I love these delicate posts.
wedding dress patterns plus size free
Nice post.
new coach bags 2014
nice site, all posts are very nice.
herve leger gold foil jewellery
I love this post !! totally kewl!!! Well done! I’m coming back to this one ¡
ray ban aviators black frame green lens kullananlar
wonderful post, thank you.
halter camo wedding dresses
Thanks for such a great post and the review, I am totally impressed!
coach discount uk
more wait .. ;)
mens louis vuitton resale
thanks, nice post.
giuseppe zanotti nyc showroom address
Interesting site.
gafas ray ban 4068
Thanks ! Supper Post !!
ray-ban wayfarer folding sunglasses rb4105
JUST AWESOME!!!!!!Gr888 Job
wedding dresses 6th ave tacoma
Thanks for such a great post and the review, I am totally impressed!
executive coach repair
So cool! Thanks.
nike air max 180 london
a very successful site. Also very revealing article. Thanks to the contributors.
vintage wedding dresses in london
Thanks for sharing this, its great :)
nike coach catalog
I greatly appreciate all the info I’ve read here. I will spread the word about your blog to other people. Cheers.
authentic herve leger dress sale australia
Thanks. Very nice post. Your web site is very beautiful.
coach shoes loafers
Excellent post. Thanks.
ray ban original wayfarer asian fit
Good post, I always like them.
mens louis vuitton wallet
Thank for very good work!
giuseppe zanotti black and white stripe
wonderful post, thank you.
lace wedding dresses for sale
nice post,thanks for share.
ray ban 4039 polarizado
This is good, helps me a lot, thanks.
champagne colored ball gown wedding dresses
This post is so help to me! Thanks for share.
ray ban 3025 gold l0205
Great post! Thx.
coach legacy purses
Thanks. Very nice post. Your web site is very beautiful.
coach poppy purse purple
hey good job man.