【BZOJ 4716】假摔

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4716
神犇题解:http://blog.csdn.net/pure_w/article/details/53428070

解题报告

我们注意到权值是非负的
于是我们先把每一个点作为右上角的最小矩阵扔到小根堆中
之后每一次取出最小的,拓展一行一列,之后再扔回去就可以辣!

一开始没有看到权值非负
以为要像超级钢琴一样用个数据结构维护什么的
结果活生生没有想出来 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;

int n,m,mnx,mny,k,arr[N][N],sum[N][N];
struct Squre{
	int x,y,lx,ly,val;
	inline bool operator < (const Squre &B) const {
		return val > B.val;
	}	
}; 
priority_queue<Squre> que;	
set<pair<int,int> > s[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 int cal(int x, int y, int lx, int ly) {
	return (LL)sum[x][y] - sum[x][y-ly] - sum[x-lx][y] + sum[x-lx][y-ly];
} 

int main(){
	m = read(); n = read();
	mny = read(); mnx = read(); k = read();
	for (int j=1;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			arr[i][j] = read(); 
			sum[i][j] = (LL)sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j];
			if (i >= mnx && j >= mny) 
				que.push((Squre){i,j,mnx,mny,cal(i, j, mnx, mny)});
		}
 	}
 	for (int i=1;i<k;i++) {
		Squre w = que.top(); que.pop();
		if (w.x > w.lx && !s[w.x][w.y].count(make_pair(w.lx+1, w.ly))) {
			que.push((Squre){w.x,w.y,w.lx+1,w.ly,cal(w.x,w.y,w.lx+1,w.ly)});
			s[w.x][w.y].insert(make_pair(w.lx+1, w.ly));
		}
		if (w.y > w.ly && !s[w.x][w.y].count(make_pair(w.lx, w.ly+1))) {
			que.push((Squre){w.x,w.y,w.lx,w.ly+1,cal(w.x,w.y,w.lx,w.ly+1)});
			s[w.x][w.y].insert(make_pair(w.lx, w.ly+1));
		}
	}
	printf("%d\n",que.top().val+1);
	return 0;
}

后记

现在问题来了,如果权值可以为负数怎么做?

28 thoughts to “【BZOJ 4716】假摔”

  1. Great beat ! I wish to apprentice even as you amend your website, how
    could i subscribe for a blog web site? The account helped
    me a applicable deal. I were a little bit familiar of this your broadcast
    provided vibrant transparent idea

  2. Hi there! I could have sworn I’ve been to this blog before but
    after browsing through some of the post I realized it’s new to me.

    Anyhow, I’m definitely delighted I found it and I’ll be bookmarking and checking back frequently!

  3. We are a gaggle of volunteers and opening a new scheme in our community.
    Your site provided us with useful information to work on.
    You’ve done an impressive job and our entire neighborhood
    might be thankful to you.

  4. I don’t know whether it’s just me or if perhaps everyone else encountering problems with
    your blog. It looks like some of the written text on your posts are running off the
    screen. Can somebody else please comment and let me know if this
    is happening to them too? This could be a issue with my internet browser because I’ve had this happen before.
    Cheers

  5. Undeniably believe that which you stated.
    Your favorite justification appeared to be on the internet
    the simplest thing to be aware of. I say to you,
    I definitely get annoyed while people think about worries that they just don’t know
    about. You managed to hit the nail upon the top and defined out the whole thing without having side effect , people could take a signal.
    Will probably be back to get more. Thanks

  6. I have learn several good stuff here. Definitely worth bookmarking for
    revisiting. I wonder how so much effort you set to make any such magnificent informative website.

  7. I got what you mean , appreciate it for putting up.Woh I am lucky to find this website through google. “Money is the most egalitarian force in society. It confers power on whoever holds it.” by Roger Starr.

  8. Hey there! I understand this is somewhat off-topic but
    I needed to ask. Does building a well-established blog like yours take a massive amount work?
    I am completely new to running a blog but I do write in my journal daily.
    I’d like to start a blog so I can easily share my personal experience and thoughts online.
    Please let me know if you have any kind of suggestions or tips for new aspiring bloggers.
    Appreciate it!

  9. Heya! I’m at work surfing around your blog from my new apple iphone!
    Just wanted to say I love reading your blog and look forward to all your posts!

    Keep up the great work!

  10. An impressive share! I have just forwarded this onto a colleague who has been conducting a little research on this.

    And he actually bought me breakfast simply because I stumbled upon it for him…
    lol. So allow me to reword this…. Thanks for the meal!!
    But yeah, thanx for spending some time to talk about this
    issue here on your web site.

  11. Good day! I simply wish to offer you a big
    thumbs up for your great information you have right here on this post.
    I will be coming back to your blog for more soon.

  12. For most up-to-date news you have to visit the web and on internet I found
    this site as a most excellent site for most up-to-date updates.

  13. whoah this weblog is fantastic i like studying your articles.
    Stay up the good work! You know, many individuals are hunting around for this information,
    you can aid them greatly.

  14. Howdy would you mind letting me know which web host you’re using?
    I’ve loaded your blog in 3 different web browsers and I must say this blog loads a lot quicker then most.
    Can you recommend a good web hosting provider at a honest price?
    Thank you, I appreciate it!

  15. Magnificent goods from you, man. I have understand
    your stuff previous to and you are just extremely fantastic.
    I actually like what you have acquired here, certainly like what you are saying
    and the way in which you say it. You make it enjoyable
    and you still take care of to keep it wise.

    I can not wait to read much more from you. This is actually a tremendous site.

  16. There are certainly quite a lot of particulars like that to take into consideration. That is a great point to convey up. I offer the thoughts above as normal inspiration but clearly there are questions like the one you deliver up where a very powerful factor shall be working in trustworthy good faith. I don?t know if best practices have emerged round things like that, however I am positive that your job is clearly identified as a fair game. Each boys and girls really feel the affect of just a second’s pleasure, for the rest of their lives.

Leave a Reply

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