سلام . از اونجایی که سوال A یکم سخته بذارین حلش کنیم :


تو سوال گفته اگه عدد x ای انتخاب بشه تمام اعداد x-1 و x+1 حذف میشه . از اینجا میشه متوجه شد که ما از 3 عدد پشت سر هم فقط میتونیم یکی از اعداد رو والبته همش رو انتخاب کنیم . چون وقتی مثلا 2 رو انتخاب میکنیم ، همه ی 1 ها و 3 ها حذف میشن پس دیگه چیزی نمیمونه که 2 رو پاک کنه و ما میتونیم همشون رو انتخاب کنیم...


حالا برسیم به راه حل پویامون :

اولا جای عددا تو دنباله مهم نیست و فقط تعداد مهمه ، پس ما میایم تو یه آرایه تعداد هر عدد رو ذخیره میکنیم : 

int n;

long long int c[100005] = {};

cin>>n;

for (int i=0,x ; i<n ; i++)

{

cin>>x;

c[x]++;

}


حالا مسئله رو از عدد 1 شروع میکنیم به حل کردن اینجوری که وقتی رو عدد i هستیم فرض میکنیم فقط و فقط اعداد 1 تا i رو داریم و هیچ عدد دیگه ای وجود نداره ، اینجوری مسئله ساده تر میشه . 

برای هر عدد تو یه آرایه به اسم dp بهترین جواب ممکن تا اون بازه رو ذخیره میکنیم . 


برای 1 ، dp[1]= count1 هستش ( چون گفتیم رو هر عدد فقط خودش و عددای قبلش رو داریم ) . برای بقیه ی اعداد دو حالت وجود داره :


1 - i رو انتخاب کنیم : اگه i رو انتخاب کنیم میدونیم که نمیتونیم i-1 رو انتخاب کنیم . پس میتونیم از بهترین جواب بازه ی 1 تا i-2 و خود عدد i استفاده کنیم .

2 - i رو انتخاب نکنیم :  پس میتونیم از بهترین جواب تو بازه ی 1 تا i-1 استفاده کنیم .


ماکزیمم این دو تا عدد میشه جواب برای اعداد تو بازه ی 1 تا i .


میتونید کدش رو ببینید . (سعی کنید خودتونم دوباره کدشو بنویسین)