【BZOJ 1024】[SCOI2009] 生日快乐

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1024

算一算发现状态只有五六百种的样子
再加上每个状态的转移只有不超过10个
于是就可以记忆话搜索辣!
然而似乎直接暴搜也可以过 (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const double INF = 1e9;
const double EPS = 1e-3;

struct Data{
	double x,y,val;
	inline Data() {}
	inline Data(double x, double y, double val):x(x),y(y),val(val) {
		if (x < y) swap(x, y);
	}
	inline bool operator < (const Data &tmp) const {
		if (abs(tmp.x - x) < EPS && abs(tmp.y - y) < EPS) return 0;
		else if (tmp.x - x > EPS) return 1;
		else if (x - tmp.x > EPS) return 0;
		else if (tmp.y - y > EPS) return 1;
		else return 0;  
	}
};
set<Data> S;
set<Data>::iterator itr;

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;
}

double DFS(double x, double y, int n) {
	if (n == 1) {
		if (x < y) swap(x, y);
		return x / y; 
	} else {
		itr = S.find(Data(x,y,0));
		if (itr != S.end()) return itr->val;
		else {
			double ret = INF;
			for (int i=1;i*2<=n;i++) {
				ret = min(ret, max(DFS(x*i/n,y,i), DFS(x*(n-i)/n,y,n-i)));
				ret = min(ret, max(DFS(x,y*i/n,i), DFS(x,y*(n-i)/n,n-i)));
			}
			S.insert(Data(x,y,ret));
			return ret;
		}
	}
}

int main(){
	int x=read(),y=read(),n=read();
	printf("%.6lf\n",DFS(x,y,n));
	return 0;
}

24 thoughts to “【BZOJ 1024】[SCOI2009] 生日快乐”

  1. Just desire to say your article is as astounding. The clarity in your post is simply
    great and i could assume you’re an expert on this subject.

    Well with your permission allow me to grab your feed to keep up to date with forthcoming post.
    Thanks a million and please continue the gratifying work.

  2. You’re so cool! I don’t think I have read through something like this before.

    So wonderful to find someone with original thoughts on this topic.
    Seriously.. thank you for starting this up. This site is something that
    is required on the internet, someone with some originality!

  3. Good post but I was wanting to know if you could write a litte more on this topic?
    I’d be very grateful if you could elaborate a little bit more.
    Many thanks!

  4. I blog quite often and I really thank you for your content.
    This article has really peaked my interest. I will book mark your site and keep
    checking for new details about once a week. I subscribed to your RSS feed as well.

  5. My spouse and I stumbled over here coming from a different web
    address and thought I may as well check things out.
    I like what I see so now i am following you. Look forward to checking out your web page yet
    again.

  6. Everything is very open with a really clear clarification of the issues.
    It was truly informative. Your site is very helpful.
    Many thanks for sharing!

  7. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically
    tweet my newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would
    have some experience with something like this.
    Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new updates.

  8. An impressive share! I’ve just forwarded this onto a coworker who was doing a little homework on this.
    And he in fact bought me dinner due to the fact that I found
    it for him… lol. So let me reword this…. Thank YOU
    for the meal!! But yeah, thanks for spending some time to discuss this subject here on your web page.

  9. Great article and straight to the point. I am not sure if this is in fact the best place to ask but do you guys have any ideea where to get some professional writers? Thanks 🙂

  10. Hey there! This is my first visit to your blog!

    We are a team of volunteers and starting a new initiative in a community in the same niche.

    Your blog provided us beneficial information to work on. You have done a wonderful job!

  11. I am really impressed with your writing skills as well as
    with the layout on your weblog. Is this a paid theme
    or did you customize it yourself? Anyway keep up the nice quality writing, it’s
    rare to see a nice blog like this one today.

  12. Have you ever thought about creating an e-book or guest
    authoring on other blogs? I have a blog based upon on the same topics you discuss and would really like to have you share some stories/information. I
    know my viewers would enjoy your work. If you’re even remotely interested, feel
    free to send me an email.

  13. I’m not sure exactly why but this weblog is loading incredibly slow for me.
    Is anyone else having this issue or is it a problem on my end?
    I’ll check back later and see if the problem still exists.

  14. My coder is trying to convince me to move to .net from PHP.
    I have always disliked the idea because of the expenses.

    But he’s tryiong none the less. I’ve been using Movable-type on a variety of websites
    for about a year and am concerned about switching to another platform.
    I have heard very good things about blogengine.net.

    Is there a way I can transfer all my wordpress content
    into it? Any help would be really appreciated!

  15. whoah this weblog is excellent i really like studying your articles.
    Keep up the good work! You recognize, many people are looking
    round for this info, you can help them greatly.

Leave a Reply to match.com free trial Cancel reply

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