相关链接
题目传送门: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; }
后记
现在问题来了,如果权值可以为负数怎么做?
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
I always used to read article in news papers but now as I am a user of internet so from now I am
using net for posts, thanks to web.
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!
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.
It’s fantastic that you are getting ideas from this post as well
as from our argument made at this time.
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
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
Excellent way of describing, and good article to get data concerning my presentation topic, which i am going to convey in college.
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.
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.
This is my first time pay a visit at here and i am genuinely pleassant to read everthing
at one place.
You really make it seem so easy with your presentation but I find this matter to be really something which I think
I would never understand. It seems too complex and extremely broad for me.
I am looking forward for your next post, I’ll try to get
the hang of it!
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!
I visited multiple web sites except the audio
feature for audio songs present at this web page is really wonderful.
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!
What’s up, just wanted to say, I enjoyed this blog post.
It was practical. Keep on posting!
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.
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.
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.
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.
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!
Way cool! Some extremely valid points! I appreciate you writing this article
and the rest of the website is also very good.
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.
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.
I’ll always visit here because it’s fun and I have more information available. I can use it once in the day and share with my acquaintances and friends
Really This goes far beyond the commenting! It wrote his thoughts while reading the article amazingly.kindly visit us.
What’s up to every one, it’s really a nice for me to pay a visit this web page, it consists of important Information.
I have been checking out many of your stories and i can state pretty