题目传送门：http://42.247.7.121/zh/Problem/Details/2922
离线版题目：http://paste.ubuntu.com/23198035/
数据生成器：http://paste.ubuntu.com/23198038/
这题真的是好妙！点个大赞！
题解让我们召唤黄学长：http://hzwer.com/3308.html
另外，我的这份代码的复杂度多了一个k，要想速度快就去抄黄学长的代码吧！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m,k,cnt,dis[10010],sz[200],pos[30],f[1200000],cost[30][30];
queue<int> que;
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 BFS(int W, int num) {
memset(dis,127,sizeof(dis));
que.push(W); dis[W] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=1;i<=m;i++) {
if (w+sz[i] <= n+1 && dis[w+sz[i]] > dis[w]+1) dis[w+sz[i]] = dis[w]+1, que.push(w+sz[i]);
if (w-sz[i] >= 1 && dis[w-sz[i]] > dis[w]+1) dis[w-sz[i]] = dis[w]+1, que.push(w-sz[i]);
}
}
for (int i=1;i<=cnt;i++) cost[num][i] = dis[pos[i]];
}
int main(){
n = read(); k = read(); m = read();
for (int i=1;i<=k;i++) dis[read()] = 1;
for (int i=1;i<=m;i++) sz[i] = read(); sort(sz+1,sz+1+m); m = unique(sz+1,sz+1+m) - sz - 1;
for (int i=1;i<=n+1;i++) if (dis[i] + dis[i-1] == 1) pos[++cnt] = i;
for (int i=1;i<=cnt;i++) BFS(pos[i],i);
memset(f,127,sizeof(f));
f[(1<<cnt)-1] = 0;
for (int w=(1<<cnt)-1;w;w--) if (f[w] < 1e9)
for (int i=1;i<=cnt;i++) if (w&(1<<i-1)) for (int j=i+1;j<=cnt;j++) if (w&(1<<j-1) && cost[i][j] < 1e9)
f[w^(1<<i-1)^(1<<j-1)] = min(f[w^(1<<i-1)^(1<<j-1)],f[w]+cost[i][j]);
printf("%d\n",f[0]>1e9?-1:f[0]);
return 0;
}
Fantastic blog you have here but I was curious about if you knew
of any discussion boards that cover the same
topics discussed in this article? I’d really love to be a part of
group where I can get opinions from other knowledgeable individuals
that share the same interest. If you have any suggestions, please
let me know. Cheers!
Magnificent goods from you, man. I have understand your stuff previous to and you’re just too fantastic.
I actually like what you have acquired here, really like what you’re
saying and the way in which you say it. You make it enjoyable and you
still care for to keep it smart. I can’t wait to read much more from you.
This is really a terrific web site.
Greetings from Florida! I’m bored to tears at work so
I decided to check out your blog on my iphone during lunch break.
I enjoy the information you provide here and can’t wait to take a
look when I get home. I’m shocked at how quick your blog
loaded on my cell phone .. I’m not even using WIFI,
just 3G .. Anyways, very good blog!
Hi there, of course this piece of writing is genuinely fastidious and
I have learned lot of things from it about blogging. thanks.
I do trust all of the ideas you have offered to your post.
They are really convincing and will certainly work.
Still, the posts are too short for starters. May just you please prolong
them a little from subsequent time? Thank you for the post.
Generally I do not learn post on blogs, however I would like
to say that this write-up very compelled me to take a look at and
do it! Your writing taste has been amazed me. Thanks, quite nice article.
Marvelous, what a website it is! This weblog gives useful information to
us, keep it up.
For hottest information you have to pay a visit world-wide-web and on internet I found this site as a best website for newest updates.
Howdy! Someone in my Facebook group shared this website with
us so I came to check it out. I’m definitely enjoying the information.
I’m bookmarking and will be tweeting this to
my followers! Superb blog and superb design.
Hurrah! In the end I got a website from where I be capable of in fact obtain useful information regarding my study
and knowledge.
First of all I want to say great blog! I had a quick question which I’d like to ask
if you don’t mind. I was curious to find out how you center yourself and clear your thoughts prior to writing.
I’ve had a difficult time clearing my thoughts in getting my
thoughts out there. I do take pleasure in writing however
it just seems like the first 10 to 15 minutes are usually lost just trying
to figure out how to begin. Any ideas or hints? Cheers!
I wanted to write you that little observation to be able to say thank you as before for your incredible views you have featured on this page. This is really shockingly open-handed of you to supply publicly precisely what most of us might have sold for an e book to make some cash for their own end, most importantly seeing that you might have tried it in the event you wanted. These guidelines additionally acted like the fantastic way to be sure that most people have a similar interest just like mine to know the truth a great deal more regarding this matter. I am sure there are a lot more pleasant situations up front for people who discover your blog.
Keep on working, great job!
I am truly thankful to the owner of this website who has shared this wonderful article at at this place.
Asking questions are actually good thing if you are
not understanding anything totally, but this piece of writing provides nice understanding yet.
Hi! I’m at work browsing your blog from my new iphone 4!
Just wanted to say I love reading through your blog and
look forward to all your posts! Keep up the superb work!
Thank you for sharing your info. I really appreciate your efforts and I will be waiting for
your next write ups thanks once again.
It’s awesome to pay a quick visit this web page and reading the views of all colleagues regarding this article, while I am also eager of
getting experience.
It’s going to be end of mine day, however before
finish I am reading this great paragraph to improve my
experience.
It’s amazing in support of me to have a website, which is valuable designed for my
knowledge. thanks admin
If you want to take a good deal from this piece of writing
then you have to apply these strategies to your
won blog.
Keep this going please, great job!
I really appreciate this post. I have been looking everywhere for this! Thank goodness I found it on Bing. You’ve made my day! Thanks again