جدی؟ سوالش آسون نیست ها! حواستون باشه جوب نزنین! (اگه مموریت n^2 باشه ۳۲ مگ کافیه.)
2015-01-02 05:07:35 -0500 محمد مهدیآمار پرسش:
- پرسیده شده: 2015-01-01 12:15:35 -0500
- مشاهده شده: 372 بار
- بروز شده: 2015-01-03 04:26:56 -0500
پرسش‌های مشابه:
تعداد راه‌های افراز عدد ۱۰۰ به اعداد کوچکتر از خود
جزوه‌ی برنامه‌نویسی (داینامیک)
پیدا کرن جدولی برای قلی در بازی مرگ و زندگی
جعبه های مهره و آقوی همساده !-مسئله F ای سی ام دانشگاه فردوسی
شمردن تعداد نا به جایی ها در یک آرایه - کدینگ
پوش محدب - کدینگ -سوال سخت -الگوریتمی (Convex Hull)
سوال کدینگ - مسئله 104 sgu -سوال سخت
سوال کدینگ - dp - فارسی - سوال سخت
سوال کدینگ تقریبا فنننننی !!!!
آیا میتوان با جمع m عدد اول عدد n را ساخت؟
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
ماتریسی از 0 و 1 ( کدینگ )
یک ماتریس n*n با درایه های 0 و 1 داریم ..
مساحت بزرگترین مستطیلی که هیچ درایه 1 ندارد چند است؟
n<=2000
ورودی نمونه:
5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
خروجی نمونه: 9
Time limit = 2 S
Memory limit = 32 MB
2015-01-01 12:15:35 -0500
تاکسیران 973 ● 6 ● 12 ● 28
نظرات
1 پاسخ
یکمم توضیح :
در آرایه ی [h[i][j داریم که اولین یک بالاتر از خونه ی iوj چندتا بالاتره (بیرون جدول یکه)
حالا مستطیل جواب رو در نظر بگیرید حتما یه یک بالای اون قرار داره که مانع گسترشش بشه
حالا با ازای هر خونه بزگترین مساحتی رو بدست می آوریم که این روی ضلع پایینی اش باشه و ارتفاع اون برابر [h[i][j باشه:)
(یعنی هر مستطیل جواب یه سنگ بالاش داره که ما از خونه ای این مستطیل رو بدست میاریم که هم مجاور ضلع پایینی اش باشه و با اون سنگه هم ستونی باشه)
حالا می خواهیم ببینیم که این مستطیل ما طولش (ضلع پایینی اش ) اندازه اش چه قدره :
بدیهی که از سمت راست تا جایی ادامه داره که یه سنگی داخل مستطیل بیافته و از سمته چپم همین طور
یعنی تا جایی که h اش کمتر از ما باشه
که اونم با یه استک ok میشه
برای اینکه مموری هم نشیم در جا هر سطرو کارشو می سازیم تا از آرایه ی اضافی جلوگیری کنیم.
امیداورم که مفید باشه :)
2015-01-02 06:59:12 -0500
طوفان 1480 ● 11 ● 21 ● 43
نظرات
ایده سوال همین بود . دارم برات تستر می نویسم تا 10 دقیقه دیگه نتیجرو می گم. 1+
2015-01-02 07:09:33 -0500 تاکسیران