Shopping Mania

জিততে হলে যেহেতু প্রতিযোগীকে অন্য প্রতিযোগী থেকে বেশী বা সমান স্কোর তুলতে হবে, এবং যেহেতু অন্য প্রতিযোগী বিচক্ষণের মতন খেলবে ধরে নেয়া যায়, আমাদের বের করা উচিত প্রতিযোগীতার যেকোন স্টেজে বর্তমান প্রতিযোগীর স্কোর থেকে অন্য প্রতিযোগীর বিয়োগফল সর্বোচ্চ কত হতে পারে। বিয়োগফল যদি অঋণাত্মক হয়, তাহলে বর্তমান প্রতিযোগী অবশ্যই জিতবে। নাহলে, যদি অন্য প্রতিযোগী বিচক্ষণের মতন খেলে, সে জিতবে।

ধরো কোন এক দানে, একজন প্রতিযোগী দেখল বস্তু $i$ বিক্রয় হবে এবং আর সর্বোচ্চ $j$ টি স্কিপ বাকি আছে। সে স্কিপ করতে পারে বা ক্রয় করতে পারে। ধরো $dp(i, j)$ হচ্ছে বর্তমান প্রতিযোগীর স্কোর এবং অন্য প্রতিযোগীর স্কোরের সর্বোচ্চ বিয়োগফল। তাহলে এমন মুভ দেওয়া উচিত যাতে $dp(i, j)$ এর মান সর্বোচ্চ হয়।

• ক্রয় করাঃ কিনলে বিয়োগফল হয় $p_i - dp(i + 1, k)$।

• এড়িয়ে যাওয়াঃ যদি $j > 0$ হয়, তবে এড়িয় গেলে বিয়োগফল $-dp(i, j-1)$।

আমরা ধরে নিতে পারি, $dp(n + 1,k) = 0$। যদি $j = 0$ হয়, তাহলে বর্তমান প্রতিযোগীকে অবশ্যই ক্রয় করতে হবে। অন্যথায় যদি $p_i - dp(i + 1, k) < -dp(i, j - 1$ হয়, তবে সে স্কিপ করতে পারে।

শাপলার প্রথমে যাওয়া উচিত যদি $dp(1, k) >= 0$ হয়, অন্যথায় পরে।