【BZOJ 2794】[POI2012] Cloakroom

链接

题目传送门: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;
}

23 thoughts to “【BZOJ 2794】[POI2012] Cloakroom”

  1. 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!

  2. 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.

  3. 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.

  4. 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!!

  5. 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

  6. 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.

  7. 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!

  8. 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.

  9. 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!

  10. 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.

  11. 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!

  12. 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!

  13. 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!

  14. 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.

Leave a Reply to sling tv Cancel reply

Your email address will not be published. Required fields are marked *