题目传送门：http://codeforces.com/contest/711/problem/C
数据生成器：http://paste.ubuntu.com/23124114/
官方数据：http://codeforces.com/blog/entry/46830
O(n^4)的DP还是很好想，但这货的细节比较多，我调了3个小时![FS~3Z]@~(4B0{S~)AKZ2G88](http://oi.cyo.ng/wp-content/uploads/2016/08/FS3Z@4B0SAKZ2G88.jpg)
然后是可以优化到O(n^3)，因为只有相不相等才影响答案，所以只用记录最小的两种颜色即可
嘴巴上AC还是很容易的，但代码写起来更恶心，所以弃疗![QRRXCIEEY4QTA4`}]CL@RVL](http://oi.cyo.ng/wp-content/uploads/2016/08/QRRXCIEEY4QTA4CL@RVL.jpg)
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 100+9;
const int INF = 1000000000+9;
int q[N][N],n,m,K,arr[N],cur,w,p;
LL f[2][N][N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
inline void update(LL &w, LL sta) {
if (!w || sta < w) w = sta;
}
int main(){
n = read(); m = read(); K = read();
for (int i=1;i<=n;i++) {
arr[i] = read();
if (!arr[i-1]) cur += (arr[i] > 0);
else cur += (arr[i] != arr[i-1] && arr[i] != arr[i+1]);
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) q[i][j] = read();
if (!arr[1]) for (int j=1;j<=m;j++) {
if (j != arr[2]) f[p][j][cur+1] = q[1][j]+1;
else f[p][j][cur] = q[1][j]+1;
} else f[p][arr[1]][cur] = 1; w = 1;
for (int i=2;i<=n;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
if (arr[i]) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++)
{if (f[p][j][k]) update(f[w][arr[i]][k],f[p][j][k]);}
else for (int j=1;j<=m;j++) {
for (int k=1;k<=n;k++) for (int t=1;t<=m;t++) if (f[p][t][k])
if (j != t) update(f[w][j][k+(j != arr[i+1])],f[p][t][k] + q[i][j]);
else update(f[w][j][k-(j == arr[i+1])],f[p][t][k] + q[i][j]);
}
}
LL vout = 0;
for (int i=1;i<=m;i++) if (f[p][i][K])
update(vout, f[p][i][K]);
if (!vout && cur != K) cout<<-1;
else cout<<vout-1;
return 0;
}
I am really impressed with your writing skills and also with the layout on your weblog.
Is this a paid theme or did you modify it yourself? Either
way keep up the nice quality writing, it’s rare to see a great blog like this one
these days.
This is my first time visit at here and i am truly impressed to read
all at one place.
whoah this blog is magnificent i like reading your articles.
Keep up the good work! You recognize, many individuals are searching round for this information, you could aid
them greatly.
Thank you, I have recently been searching for info about this subject for ages
and yours is the greatest I have discovered till now. But, what concerning the conclusion? Are you
positive concerning the source?
Very good website you have here but I was wanting to know if you knew of any message boards
that cover the same topics talked about here?
I’d really like to be a part of group where I can get opinions from other
experienced individuals that share the same interest. If you have any
recommendations, please let me know. Bless you!
With havin so much content and articles do you ever run into any
problems of plagorism or copyright violation? My website has a lot of exclusive
content I’ve either written myself or outsourced but it appears a lot of it
is popping it up all over the web without my authorization. Do you know any solutions to help reduce content from being ripped off?
I’d definitely appreciate it.
I’m very happy to discover this web site.
I need to to thank you for ones time just for this wonderful read!!
I definitely loved every little bit of it and I have you book marked to look
at new information in your site.
Hello, Neat post. There is a problem along with your
website in internet explorer, could check this? IE still is the marketplace leader and a huge
component to other folks will pass over your magnificent writing because of this problem.
Generally I don’t learn article on blogs, but I
would like to say that this write-up very forced me to
check out and do so! Your writing taste has been amazed me.
Thank you, very great article.
Wow, superb blog structure! How lengthy have you ever been blogging for?
you made blogging glance easy. The total look of your web site is magnificent, let
alone the content!
I’d like to thank you for the efforts you’ve put
in writing this blog. I am hoping to see the same high-grade blog posts from you in the future as well.
In fact, your creative writing abilities has encouraged me
to get my very own website now 😉
Hey there, I think your site might be having browser compatibility issues.
When I look at your website in Safari, it looks fine but when opening in Internet
Explorer, it has some overlapping. I just wanted to give you a quick heads up!
Other then that, wonderful blog!
If some one wishes expert view regarding blogging and site-building after that i propose him/her to visit this weblog, Keep up the fastidious work.
Thank you for any other great article. Where else may just anyone get that kind
of information in such an ideal manner of
writing? I’ve a presentation subsequent week, and I’m on the look for such
information.
Hello to all, it’s actually a nice for me to visit this web
page, it contains valuable Information.
If you are going for best contents like me, just
go to see this web site every day for the reason that it provides feature contents,
thanks
of course like your web site however you need to test the spelling
on several of your posts. A number of them are rife
with spelling problems and I to find it very bothersome to inform the truth
on the other hand I will definitely come again again.
At this moment I am ready to do my breakfast, later than having my breakfast coming yet again to
read more news.
Hi there, the whole thing is going fine here and ofcourse every one is sharing information, that’s really fine, keep up writing.
For most recent news you have to pay a visit world wide web and
on the web I found this website as a best web page for hottest updates.
For hottest information you have to pay a visit the web and on internet I found this site as a finest
website for hottest updates.
This is really interesting, You are a very professional blogger.
I’ve joined your feed and look forward to searching for more of
your great post. Additionally, I have shared your web site in my social networks
Thank you, I’ve just been searching for info about this topic for ages and yours is the best I’ve discovered so
far. However, what concerning the conclusion? Are you certain concerning the source?
Hi there, this weekend is nice for me, because this time i am reading this enormous educational piece of writing here at my residence.
Hello I am so glad I found your weblog, I really found you by accident, while I was browsing on Askjeeve for something else,
Nonetheless I am here now and would just like to say thank you for a tremendous post and a
all round exciting blog (I also love the theme/design),
I don’t have time to look over it all at the moment but I have
bookmarked it and also added in your RSS feeds, so when I have time I
will be back to read a lot more, Please do keep up the fantastic
work. plenty of fish natalielise
Hi there, I read your blogs daily. Your humoristic
style is awesome, keep doing what you’re doing!
pof natalielise
What’s up, I desire to subscribe for this weblog to get most up-to-date updates, therefore where can i do
it please help.
Good site you have got here.. It’s hard to find high-quality writing like yours nowadays.
I honestly appreciate people like you! Take care!!
Hey there! I know this is kind of off topic but I was wondering which blog platform are you using
for this website? I’m getting sick and tired of WordPress because I’ve had problems with hackers and I’m looking at options for
another platform. I would be fantastic if you could point me in the direction of a good platform.
Ahaa, its pleasant dialogue concerning this article at this place at this website, I have read all that,
so now me also commenting at this place. natalielise pof
Thanks for your marvelous posting! I really enjoyed reading it,
you’re a great author. I will remember to bookmark
your blog and will eventually come back at some point. I want to encourage you to
definitely continue your great posts, have a nice morning!
Hello my loved one! I wish to say that this post is awesome, nice written and include approximately
all significant infos. I would like to peer extra posts like this .
This post is genuinely a fastidious one it helps new internet viewers, who are wishing for
blogging.
It’s appropriate time to make some plans for the future and it’s time
to be happy. I’ve read this post and if I could I want to suggest you
few interesting things or advice. Maybe you could write next articles referring to this article.
I want to read even more things about it!
Genuinely no matter if someone doesn’t know after
that its up to other visitors that they will assist, so here
it takes place.
Heya i’m for the first time here. I found this board and I to find It truly useful & it helped me out
a lot. I’m hoping to provide something back and help others like you helped me.
Hey very nice blog!
Wow! This blog looks just like my old one! It’s on a
totally different subject but it has pretty much the same page layout and
design. Excellent choice of colors!
you’re actually a just right webmaster. The web site loading pace is amazing.
It sort of feels that you are doing any distinctive trick.
Furthermore, The contents are masterpiece. you have performed a wonderful activity in this subject!
I’m pretty pleased to uncover this site. I
need to to thank you for your time for this fantastic read!!
I definitely really liked every part of it and i also have you saved to fav to see new
things in your web site.
It’s hard to come by knowledgeable people for
this subject, however, you sound like you know what you’re talking about!
Thanks
Very good blog post. I absolutely love this site.
Stick with it!
Hi! I know this is somewhat off-topic but I needed to ask.
Does running a well-established website like yours take
a large amount of work? I am brand new to blogging however I do write in my diary daily.
I’d like to start a blog so I can easily share my personal experience
and feelings online. Please let me know if you have any ideas or tips for new aspiring
blog owners. Thankyou!
hello there and thank you for your information – I have certainly picked up anything new from right here.
I did however expertise several technical issues using this web site, as
I experienced to reload the site a lot of times previous to I could get it to
load correctly. I had been wondering if your web host is OK?
Not that I’m complaining, but slow loading instances times will
sometimes affect your placement in google and can damage your quality score
if ads and marketing with Adwords. Anyway I’m adding this
RSS to my email and can look out for a lot more of your respective exciting content.
Ensure that you update this again soon.
I know this if off topic but I’m looking into
starting my own blog and was curious what all is needed to get setup?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web savvy so I’m not 100% sure. Any suggestions or advice would be greatly appreciated.
Thanks
Just want to say your article is as amazing. The clarity in your post is just great and i could assume you are an expert on this subject.
Well with your permission let me to grab your RSS feed to
keep up to date with forthcoming post. Thanks a million and please keep up the rewarding work.
Yes! Finally something about minecraft games.
Outstanding story there. What happened after?
Thanks!
I’m amazed, I have to admit. Rarely do I encounter a blog that’s
both equally educative and interesting, and without a doubt, you have hit the nail
on the head. The problem is something which too few people are
speaking intelligently about. I’m very happy I came across this during my
hunt for something concerning this.
After I originally left a comment I seem to have clicked on the -Notify me
when new comments are added- checkbox and now whenever a comment is added I get 4 emails with the same comment.
There has to be a way you are able to remove me from that
service? Appreciate it!
Hi, all is going sound here and ofcourse every one is sharing
facts, that’s in fact good, keep up writing.
Today, I went to the beach with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell
to her ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is completely
off topic but I had to tell someone!
Link exchange is nothing else except it is simply placing the other person’s website link on your page at suitable place and
other person will also do same in support of you.
If some one wishes expert view regarding running a
blog after that i propose him/her to go to see this webpage, Keep
up the good work.
I was recommended this web site by my cousin. I
am not sure whether this post is written by him as nobody else
know such detailed about my difficulty. You’re incredible!
Thanks!
Do you have a spam issue on this blog; I also am
a blogger, and I was wondering your situation; we have created some nice procedures and we are looking to swap methods with other folks,
please shoot me an e-mail if interested.
What a information of un-ambiguity and preserveness of valuable familiarity on the
topic of unpredicted feelings.
bookmarked!!, I really like your blog!
Thanks in support of sharing such a fastidious idea, paragraph is nice, thats why i have read it completely
Hi my friend! I want to say that this article is amazing, great written and include approximately all significant infos.
I would like to peer extra posts like this .
I think the admin of this site is truly working hard in favor of his
web site, for the reason that here every material is quality based material.
What’s Taking place i’m new to this, I stumbled
upon this I have found It positively useful and it has helped me out loads.
I am hoping to contribute & assist other customers like its helped me.
Great job.
There is certainly a lot to know about this subject.
I really like all of the points you have made.
My brother suggested I might like this blog. He was entirely
right. This post actually made my day. You can not imagine simply how much time
I had spent for this info! Thanks!
Great post. I was checking constantly this blog and I’m impressed!
Very useful info specially the remaining part :
) I care for such information much. I used to be seeking this particular information for a long time.
Thank you and good luck.
Great weblog here! Additionally your website loads up very fast!
What host are you the usage of? Can I get your associate hyperlink on your host?
I desire my web site loaded up as quickly as yours lol
Its not my first time to go to see this website, i am visiting this website dailly and get good information from here every day.
Hello, i read your blog from time to time and i own a similar one and i was just curious if you get a lot of
spam feedback? If so how do you prevent it, any plugin or anything you
can suggest? I get so much lately it’s driving me insane so any assistance is very much appreciated.
Link exchange is nothing else however it is only placing
the other person’s web site link on your page at appropriate place and other person will also do similar in support of you.
Wow, amazing blog format! How lengthy have you ever been running a blog
for? you made blogging look easy. The overall look of your website is great, as well as the content!
Hey there! Do you know if they make any plugins to
help with SEO? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
If you know of any please share. Cheers!
You could certainly see your skills in the work you write.
The arena hopes for more passionate writers like you who are not
afraid to say how they believe. All the time go after your heart.
Today, while I was at work, my sister stole my iphone and tested to see if it can survive a twenty five foot drop,
just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is completely off topic but I had to share it with someone!
Hey I know this is off topic but I was wondering if you
knew of any widgets I could add to my blog that automatically tweet my newest
twitter updates. I’ve been looking for a plug-in like this
for quite some time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading
your blog and I look forward to your new updates.
Very nice post. I just stumbled upon your blog and wished to say that I have really enjoyed surfing around your blog posts.
In any case I will be subscribing to your rss feed and
I hope you write again soon!
Your means of explaining everything in this paragraph is really good, all can simply know it, Thanks a lot.
Link exchange is nothing else but it is simply placing the other person’s webpage link
on your page at suitable place and other person will also do
same in support of you.
Heya i am for the first time here. I came across this board and
I to find It truly helpful & it helped me out much. I hope to
offer one thing again and aid others such as you aided me.
I was wondering if you ever thought of changing the page
layout of your site? Its very well written; I love what youve
got to say. But maybe you could a little more in the way of content so people could connect with it
better. Youve got an awful lot of text for only having
one or 2 images. Maybe you could space it out better?
If some one wishes to be updated with most recent technologies afterward he must be pay a
quick visit this website and be up to date everyday.
Hello, I enjoy reading all of your article post. I like to write a little
comment to support you.
Great weblog right here! Additionally your website a lot up fast!
What host are you the use of? Can I am getting your affiliate hyperlink for your host?
I want my website loaded up as fast as yours lol
Hey I know this is off topic but I was wondering if you knew
of any widgets I could add to my blog that automatically tweet
my newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe
you would have some experience with something like this. Please let
me know if you run into anything. I truly enjoy reading your blog
and I look forward to your new updates.
I think this is a real great blog. Much obliged.
Hey, thanks for the article post.Really thank you! Great.