راه حل ها و ایده های سوالات مسابقه نهایی ACM
۱- نصفش کن! 😐
۲- جواب برابر است با (c(p+k-1,k-1
#combinatorics
۳- صرفا یک مرتب سازی که می توانستید این کار را با (O(n^2 انجام دهید.
#sorting
۴- راه های متنوعی برای این سوال وجود دارد می توانید [dp[i][j را به این صورت تعریف کنید که برابر باشد با مجموعه خانه های [mat[k][l که k<i و l<j باشد که :
dp[i][j] = dp[i-1][j]+dp[i][j-1]- dp[i-1][j-1]+mat[i][j]
که عناصر جدول اصلی در mat‌ ذخیره شده اند.
حال جواب برابر است با:
max{dp[i][j]-dp[i][l]-dp[k][l]+dp[k][l]} (k<i,l<j,i<=n,j<=n)
که برای به دست آوردن جواب می توانستید با یک الگوریتم (O(n^4 به جواب برسید.
#Dynamic_Programming
۵- مسئله در واقع یافتن یک چند ضلعی غیر محدب و ساده است با ضلع های موازی محور های مختصات حال به با توجه به شرایط مسئله هر نقطه دقیقا یک ضلع افقی و دقیقا یک ضلع عمودی متصل به آن نقطه دارد پس تمام نقاطی که روی یک خط افقی هستند (عرض های برابر دارد) را که در نظر بگیرید و آن ها را از ۱ تا k به ترتیب شماره گذاری کنید حتما باید راس های با شماره فرد به راس های با شماره زوج سمت راست خود وصل باشند. و همین طور برای نقاط روی خط های عمودی (طول های برابر دارند) پس با مرتب کردن همه نقاط ابتدا بر اساس x و سپس بر اساس y تمام ضلع های افقی و عمودی تعیین می شود حال باید مشخص کنید که شکل حاصل یک n-ضلعی هست یا نه که این کار با یک DFS امکان پذیر است و طول چند ضلعی هم با این DFS قابل محاسبه است همچنین در صورت وجود جواب n-ضلعی به وضوح یکتا خواهد بود پس قبل از آن باید بررسی کنید که ضلع هایی که مشخص کرده اید یک دیگر را قطع نمی کنند چرا که در غیر این صورت مسئله جواب ندارد. پس این کار با (O(n^2 امکان پذیر است که این در واقع زمان مصرفی برای بررسی غیر متقاطع بودن دو به دوی ضلع های تعیین شده می باشد.
#geometry #greedy #sorting #graph #dfs #data_structure
موفق باشد
انجمن علمی علوم کامپیوتر
kermancs.ir