相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf
解题报告
假如我们钦定某个格子先取走靠左的三角形，那么其余格子是先取走靠左还是靠右就全部定下来了
于是我们暴力枚举一下，复杂度是$O(n^4)$
更进一步，我们发现：
假如我们钦定先取走$(x, y)$这个格子的靠左三角形
那么我们一定得先将$(x – 1, y)$这个格子的左三角形取走，然后再取走一些其他的三角形
于是同一行的信息是可以共用的，然后就可以记忆化搜索了
时间复杂度是$O(n^3)$的
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500;
const int INF = 1e7;
char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];
inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}
inline int F(int x, int y, int t) {
InStack[y][x] = 1;
int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));
vis[y][x] = 1;
InStack[y][x] = 0;
return ret > INF? INF: ret;
}
inline void init() {
memset(vis, 0, sizeof(vis));
for (int j = 1; j <= m; j++) {
vis[j][0] = 1;
vis[j][n + 1] = 1;
}
for (int i = 1; i <= n; i++) {
vis[0][i] = 1;
vis[m + 1][i] = 1;
}
}
int main() {
m = read(); n = read();
for (int j = 1; j <= m; j++) {
scanf("%s", mp[j] + 1);
for (int i = 1; i <= n; i++) {
up[j][i] = 1;
dw[j][i] = 0;
if (mp[j][i] == 'Z') {
swap(up[j][i], dw[j][i]);
}
}
}
for (int j = 1; j <= m; j++) {
init();
for (int i = n; i; i--) {
ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
}
init();
for (int i = 1; i <= n; i++) {
ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
}
putchar('\n');
}
return 0;
}
Good day! I know this is kinda off topic but I was wondering which blog platform are you using for
this website? I’m getting sick and tired of WordPress because I’ve
had issues with hackers and I’m looking at options for another platform.
I would be awesome if you could point me in the
direction of a good platform.
I just like the helpful info you provide on your
articles. I will bookmark your blog and take a look at once more right here frequently.
I’m rather sure I’ll be informed plenty of new stuff proper right here!
Best of luck for the next!
Definitely imagine that which you stated. Your favorite reason appeared to be at the net the simplest factor to
consider of. I say to you, I certainly get irked while other folks think about issues
that they just don’t recognize about. You managed
to hit the nail upon the highest as neatly as defined
out the entire thing without having side effect
, other people can take a signal. Will likely be back to get
more. Thank you
I was curious if you ever considered changing the page layout of your website?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way
of content so people could connect with it better.
Youve got an awful lot of text for only having one or 2 pictures.
Maybe you could space it out better?
It’s an awesome article for all the internet people; they will get advantage from it I am sure.
There is certainly a lot to find out about this issue.
I really like all the points you’ve made.
Everyone loves it when folks come together and share opinions.
Great blog, stick with it!
Incredible! This blog looks exactly like my old one! It’s on a completely different subject but
it has pretty much the same page layout and design. Great choice of colors!
It’s a pity you don’t have a donate button! I’d certainly donate to this excellent blog!
I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google account.
I look forward to brand new updates and will share this
blog with my Facebook group. Talk soon!
When some one searches for his vital thing, therefore he/she wishes to be available that in detail, thus that
thing is maintained over here.
I need to to thank you for this excellent read!!
I certainly loved every little bit of it. I have you saved as a favorite to
look at new stuff you post…
I wanted to thank you for this excellent read!!
I absolutely loved every bit of it. I’ve got you bookmarked to check
out new things you post…
It’s very trouble-free to find out any matter on net as
compared to books, as I found this piece of writing at this web site.
I’m not that much of a online reader to be honest but your blogs really nice, keep it up! I’ll go ahead and bookmark your website to come back later. Many thanks
Hi, all the time i used to check web site posts here in the early hours in the
break of day, since i like to gain knowledge of more
and more.
I couldn’t resist commenting. Perfectly written!
Good day! I just would like to offer you a big thumbs
up for the excellent info you have here on this post.
I’ll be returning to your blog for more soon.
This is a good tip especially to those fresh to
the blogosphere. Short but very precise info… Thank you for sharing this one.
A must read article!
Hi there, just became alert to your blog
through Google, and found that it’s truly informative.
I’m gonna watch out for brussels. I will be grateful if you continue
this in future. Numerous people will be benefited from your
writing. Cheers!
Hey there I am so thrilled I found your web site, I really found you by mistake, while I was researching on Bing for something else, Regardless I
am here now and would just like to say thanks a lot for a fantastic post and a all
round exciting blog (I also love the theme/design), I don’t
have time to read it all at the moment but I have bookmarked it and also included your RSS feeds, so when I have time I will be
back to read a lot more, Please do keep up the great work.
Very good website you have here but I was wanting to know if you knew of any discussion boards
that cover the same topics talked about here? I’d really like to be
a part of online community where I can get feed-back from other experienced individuals that share the same interest.
If you have any suggestions, please let me know.
Thanks!
I’ve read a few good stuff here. Certainly price bookmarking for revisiting.
I wonder how a lot attempt you place to create this type
of great informative website.
I am truly grateful to the owner of this website who has shared this great post at at this place.
I am really impressed with your writing skills and also with
the format for your weblog. Is this a paid theme or
did you modify it your self? Either way
stay up the nice quality writing, it is uncommon to see a nice
weblog like this one today..
I was suggested this web site by my cousin. I am not sure whether this post is written by him
as nobody else know such detailed about my difficulty. You
are incredible! Thanks!
I don’t even know how I ended up here, but I thought this post was good. I don’t know who you are but certainly you are going to a famous blogger if you are not already 😉 Cheers!