链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2794
数据生成器:http://paste.ubuntu.com/23946550/
神犇题解:http://trinklee.blog.163.com/blog/static/23815806020149855817630
题解
这个题目假如没有A[]和B[]的限制的话,就是一个正常的背包
然而有了这两个东西,而且复杂度要求O(1)询问,这样我就不会了 QwQ
考虑传统背包的局限性:
1)添加物品的顺序没有限制,但实际上是浪费了一些性质
2)DP的是一个bool数组,只记录是否可以凑出,这样实际上也是浪费了信息
于是考虑离线,将询问的m和物品的a[]都按照升序排好序
然后规定f[i][j]表示用前i个物品,凑出j的b[]的最小值的最大值
之后对于每个询问,A[]可以用i来限制,B[]可以直接判断
于是边DP边回答询问的话
就可以O(1)处理所有询问辣!
★,°:.☆( ̄▽ ̄)/$:.°★ 。
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000+9; const int M = 1000000+9; const int INF = 100000; struct Event{ int a,b,c,d; inline Event() {} inline Event(int _a, int _b, int _c):a(_a),b(_b),c(_c) {} inline bool operator < (const Event &B) const {return a < B.a;} }t[N],q[M]; int f[M],arr[M+N<<1],vout[M],tot,n,m,mx; inline int read() { char c=getchar(); int f=1,ret=0; 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; } int main() { n = read(); for (int i=1,a,b,c;i<=n;i++) { a = read(); b = read(); c = read(); arr[++tot] = c; arr[++tot] = b; t[i] = Event(b, c, a); } m = read(); for (int i=1,a,b,c;i<=m;i++) { a = read(); b = read(); c = read() + a; arr[++tot] = a; arr[++tot] = c; q[i] = Event(a, c, b); q[i].d = i; } sort(arr+1, arr+1+tot); tot = unique(arr+1, arr+1+tot) - arr - 1; for (int i=1;i<=n;i++) { t[i].a = lower_bound(arr+1, arr+1+tot, t[i].a) - arr; t[i].b = lower_bound(arr+1, arr+1+tot, t[i].b) - arr; mx = max(mx, t[i].a); } for (int i=1;i<=m;i++) { q[i].a = lower_bound(arr+1, arr+1+tot, q[i].a) - arr; q[i].b = lower_bound(arr+1, arr+1+tot, q[i].b) - arr; q[i].a = min(q[i].a, mx); } sort(t+1, t+1+n); sort(q+1, q+1+m); f[0] = 1e9; for (int j=1,p1=1;j<=m;j++) { for (;t[p1].a<=q[j].a&&p1<=n;p1++) { for (int i=INF-t[p1].c,to=INF;i>=0;i--,to--) { f[to] = max(f[to], min(f[i], t[p1].b)); } } vout[q[j].d] = f[q[j].c] > q[j].b; } for (int i=1;i<=m;i++) { if (vout[i]) puts("TAK"); else puts("NIE"); } return 0; }
Hi! Do you know if they make any plugins to assist 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. Appreciate it!
Simply want to say your article is as astounding.
The clearness in your publish is just excellent and i could assume you
are knowledgeable in this subject. Fine with your permission allow me to snatch your RSS feed to stay
updated with approaching post. Thank you one million and please continue the enjoyable work.
We stumbled over here by a different web page and thought I might as well check things out.
I like what I see so now i’m following you. Look forward to looking over your web page repeatedly.
Hey very nice blog!
Oh my goodness! Awesome article dude! Thank you, However
I am experiencing issues with your RSS. I don’t understand the
reason why I cannot join it. Is there anyone else having identical RSS problems?
Anyone that knows the answer can you kindly respond? Thanx!!
Thanks very nice blog!
This information is invaluable. When can I find out more?
Excellent blog here! Also your website loads up
very fast! What host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as quickly as yours lol
Hi! Someone in my Myspace group shared this website with us so
I came to give it a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
Great blog and amazing style and design.
Do you mind if I quote a few of your articles as long as I provide credit
and sources back to your blog? My blog site is in the very same area
of interest as yours and my visitors would genuinely
benefit from some of the information you present here.
Please let me know if this okay with you. Thanks a lot!
Hello I am so delighted I found your blog, I really found you by error, while I
was researching on Askjeeve for something else, Regardless I am here now and would just like to say
cheers for a tremendous post and a all round enjoyable blog (I also love the
theme/design), I don’t have time to browse it all at
the minute but I have bookmarked it and also
added your RSS feeds, so when I have time I will be back to read a
great deal more, Please do keep up the great work.
Today, I went to the beachfront 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 totally off topic but I had to tell someone!
Hi there! Someone in my Myspace group shared this website
with us so I came to give it a look. I’m definitely
enjoying the information. I’m book-marking and will be tweeting this to
my followers! Outstanding blog and superb design and style.
Hi there, You have done a great job. I’ll definitely digg it and personally suggest
to my friends. I am sure they will be benefited from this website.
An interesting discussion is definitely worth
comment. I do believe that you should write more on this topic, it may not be
a taboo matter but generally people don’t speak about such subjects.
To the next! Many thanks!!
Hi! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing many months of
hard work due to no backup. Do you have any methods to protect
against hackers?
It’s the best time to make some plans for the future and it is time to be happy.
I have read this post and if I could I desire to suggest you few interesting things or
advice. Perhaps you could write next articles referring to this article.
I want to read even more things about it!
Wow, marvelous blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your
site is fantastic, as well as the content!
Hello! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly?
My site looks weird when viewing from my iphone 4.
I’m trying to find a theme or plugin that might be able to resolve
this problem. If you have any suggestions, please share.
Cheers!
Hi! Someone in my Myspace 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! Fantastic blog and great design and style.
Hello my family member! I wish to say that this post is awesome,
great written and come with almost all vital infos.
I’d like to peer extra posts like this .
Some genuinely grand work on behalf of the owner of this website , perfectly outstanding subject material.
Thanks again for the post.Much thanks again. Will read on…