مشکل در فهم سوال (گردنبند پاره شده)

[lvlina_r]

سلام
کسی می تونه به من تو حل این سوال کمک کنه؟؟؟
گردنبند دو رنگش که کاری نداره، واسه سه رنگ چی کار کنم، اصلا چی گفته؟؟؟؟

[newamir]

میگه که یه گردنبند رو که از سه رنگ تشکیل شده از یه جا پاره میکنیم. بعد به صورت مستقیم روی میز میذاریمش. حالا از یک سر گردنبند، مهره اول را برمیداریم، اگر مهره دوم همرنگ آن بود دومی را هم برمیداریم، اگر سومی هم همرنگ بود آن را هم برمیداریم، ... تا جایی که مهره ای ناهمرنگ پیدا شود. از سر دیگر نیز همین کار را میکنیم. یعنی دو مجموعه مهره جمع میکنیم. حال سوال میخواهد که گردنبند را از جایی برش دهید که مجموعه مهره هایی که جمع کرده ایم بیشینه شود. مثلا در برش زیر:

rrrbrbbwbwbbwrrbww
دو مهره w راستی و سه مهره rrr چپی را برمیداریم. بنابراین مجموعآ 5 عضو انتخاب میکنیم.
این مساله رو به صورت خطی میشه حل کرد.
اگر ورودی رشته s باشه رشته sss رو بررسی میکنیم. یه بار از چپ به راست و یه بار از راست به چپ رشته sss رو پویش میکنیم. ابتدا L مساوی یکه. برای رفتن به گام بعد باید چک کنیم که آیا مهره i+1 با مهره i همرنگ هست یا نه. اگه بود L رو یکی زیاد میکنیم و در غیر اینصورت L رو یک میکنیم. با این روش در گام i ام L مساوی طول بلندترین زیررشته ی تک رنگی هست که به حرف i ام ختم میشه. در هرگام L رو در اندیس i ام آرایه A ذخیره میکنیم. در پایان همین کار رو از سر دیگه هم انجام میدیم و مقادیر رو در آرایه B ذخیره میکنیم. در نهایت عناصر A , B رو با هم جمع میکنیم و در C میریزیم. بزرگترین عنصر C جواب مساله است. البته اگر این عنصر از N بزرگتر بود جواب مساله همان N است.

[lvlina_r]

ممنون، ولی صورت سوال برش شده را به ما میده، درسته؟؟

منظورش این جملش پس چی می شه؟؟ تکلیف مهره های سفید
a white bead that is encountered may be treated as either red or blue and then painted with the desired color

[newamir]

بله گردنبند برش شده رو میده. منظور منم از s همونه. از این لحاظ مشکلی نیست.

ایرادی که شما گرفتین به جاست. منظور از این جمله اینه که مهره های سفید رو در صورت لزوم میشه قرمز یا آبی در نظر گرفت. مثال:
bbwbbrrrbwbrrbrwwr
میتوان rwwr را از راست و bbwbb را از چپ برداشت که مجموعآ میشود 9 مهره.
در راه حل جایی که میخواهیم L را برای گام بعدی اصلاح کنیم تغییر میکند. به این صورت که اگر مهره i+1 همرنگ یا سفید بود، L را یکی زیاد میکنیم و در غیر اینصورت L را مساوی یک میکنیم.

[lvlina_r]

می شه مثالی که آخر داده را هم تفسیر کنید
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****

[newamir]

این یه راهنمایی برای حل سواله. گفته که برای اینکه دایره ای بودن گردنبند را شبیه سازی کنید (چون باید با رشته کار کنیم). گفته که به جای ورودی s رشته ss را تحلیل کنید. اگر دقت کنید دو رشته ای که نوشته برابر هستن. یعنی آن را یک بار جلوی خودش کپی کنید. من الان متوجه شدم که برای راه حل من هم پویش ss کافی است و لازم نیست sss بررسی شود.

[lvlina_r]

آقای امیر ببینید وقتی از آخر شروع کرده با گفته ی شما فقط آبی را باید حساب کنه، جون بعدش قرمزه و تغییر رنگه، ولی این کار را نکرده، چرا؟؟؟؟؟

[newamir]

ببینید از اینجایی که با # علامت گذاشتم برش داده:
wwwbbrwrbrbrrbrbrwrwwrbwrwrr#b wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
از طرف چپ 5 مهره قرمز، و از طرف راست 6 مهره آبی (با در نظر گرفتن سفید ها) جمع شده اند.

[lvlina_r]

خوب اینجوری خیلی سخت می شه، یعنی برش تغییر پیدا می کنه .... چطوری برش را پیدا کنم؟/

[newamir]

من که گفتم راه حلش رو.
ببینید این مساله مال سایت usaco بود که من چند وقت پیش کد c شو نوشتم. البته چون در اونجا لازم زمان اجرایی n^2 کافی بود من از الگوریتم brute force ش استفاده کردم. در ضمن ورودی های مساله، همون طور که در صورت مساله خواسته شده، از فایل beads.in خوانده میشن و خروجی در beads.out ریخته میشه. اگه کدشو بخونین شاید متوجه راه حلش هم بشین.

/*
ID: amir.ju1
LANG: C++‎‎‎‎
TASK: beads
*/
//Author: Amir Joudaki

#include <iostream>
using namespace std;

int Break_R(char *beads, int k, int len) {
char c = beads[k];
int i = 0;
while(beads[k]=='w' && i<len) {
k = k < len-1 ? k+1 : 0;
i++;
}
c = beads[k];
while((beads[k]==c || beads[k]=='w') && i < len) {
i++;
k = k < len-1 ? k+1 : 0;
}
return i;
}
int Break_L(char *beads, int k, int len) {
k = k > 0 ? k-1 : len-1;
char c = beads[k];
int i = 0;
while(beads[k]=='w' && i<len) {
k = k > 0 ? k-1 : len-1;
i++;
}
c = beads[k];
while((beads[k]==c || beads[k]=='w') && i < len) {
i++;
k = k > 0 ? k-1 : len-1;
}
return i;
}
int Break(char* beads, int k, int len) {
int r = Break_R(beads, k, len),
l = Break_L(beads, k, len);

if( r + l >= len )
return len;
else
return r + l;
}
int main() {
FILE *fin, *fout;
fin = fopen("beads.in", "r");
fout = fopen("beads.out", "w");

int N, // number of beads
collectedBeads,
max = 0;

fscanf(fin, "%d", &N);
char* beads = new char[N+1]; // the beads
fscanf(fin, "%s", beads);

for(int i=0; i<N; i++) {
collectedBeads = Break(beads, i, strlen(beads));
max = max > collectedBeads ? max : collectedBeads;
}
fprintf(fout, "%d\n", max);
return 0;
}