Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۰:سوال ۱۲

سوال 12

در راهروی نقاشی‌های ارزشمند یک موزه، n تابلوی نقاشی با شماره‌های ۱ تا n در یک ردیف کنار هم به دیوار آویخته شده‌اند. یک سارق می‌خواهد از این موزه دزدی کند. او می‌داند ارزش تابلوی iام برابر vi است. به دلیل نزدیک بودن تابلوها به هم، اگر سارق تابلوی شماره i را از دیوار بکند، دو تابلوی مجاور آن با شماره‌های i1 و i+1 (در صورت وجود) پاره و بی‌ارزش می‌گردند.

هدف سارق سرقت تعدادی از تابلوهای موزه است که مجموع ارزش تابلوهای سرقتی (سود وی) بیشینه شود. P(i) را برابر بیشینه‌ی سود سارق تعریف می‌کنیم در حالتی که فقط تابلوهای شماره‌ی ۱ تا i قابل سرقت هستند. در این صورت کدام رابطه‌ی زیر برقرار است؟ (فرض کنید P(۰)=۰ و P(۱)=۰ قرارداد شده است. منظور از max(a,b)، مقدار بیشینه‌ی a و b است)

  1. P(i)=max(vi+P(i1),P(i2))
  2. P(i)=vi+max(P(i1),P(i2))
  3. P(i)=P(i1)+max(vi,P(i2))
  4. P(i)=P(i2)+max(vi,P(i1))
  5. P(i)=max(vi+P(i2),P(i1))

پاسخ

گزینه (5) صحیح است


ابزار صفحه