راه حل خطی داره خوب پس همون جوریه :)))) فکر نکنم ندونی چیه راه حلش ؟؟
2015-04-12 10:01:35 -0600 حمیدرضاهآمار پرسش:
- پرسیده شده: 2015-04-12 07:38:17 -0600
- مشاهده شده: 149 بار
- بروز شده: 2015-04-12 20:52:49 -0600
پرسش‌های مشابه:
برای مرحله سوم، تا چه سطحی باید برنامه نویسی بلد باشیم؟
اولین جمله از دنباله ی فیبوناچی که 1000رقم داشته باشد چیست؟
رتینگ در codeforces و سوالات در حد دوره و مرحله 3
سوال دوم مرحله سوم دوره 24: عبور از سد دفاعی ایران (حل شد + کد)
پاسخ سوالات مرحله 3 های دوره های قبل
کانتست برنامه‌نویسی فیلو (۲۰آذر)
آزمون عملی (مرحله سوم) المپیاد کامپیوتر چطور برگزار میشه و برای آمادگیش چیکار کنیم؟
سوال ۱ آزمون مرحله سوم دوره ۲۳
سوال ۲ آزمون مرحله سوم دوره ۲۳
سوال ۳ آزمون مرحله سوم دوره ۲۳
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
در یک جدول بزرگترین مربع به ضلع k که دارای مجموع بیشینه باشد
یک جدول n*n داریم که از اعداد مختلف پر است بزرگترین زیر مربع به طول k را بیابید که مجموع اعداد آن بیشینه باشد.
2015-04-12 07:38:17 -0600
سید علوی 1041 ● 11 ● 16 ● 35
نظرات
1 پاسخ
اول میای جمع اعداد جدول تا هر جا رو سیو میکنی به این صورت
$$ sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1] $$
بعد یه $brute force$ میزنی که این جوری واسه هر خونه جمع مربعی که این خونه پایین سمت راستش باشه رو حساب میکنی اونم با این فرمول:
$$ res[i][j]=sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k] $$
بعد بین این res ها مکس بگیر میشه جواب
$$ O(n^2) $$
2015-04-12 10:18:34 -0600
حمیدرضاه 2979 ● 20 ● 26 ● 52
نظرات