Düzbucaqlının boyanması#9050
Seryoja, m sıra (0-dan m-1-ə qədər nömrələnmiş) və n sütun (0-dan n-1-ə qədər nömrələnmiş) olan düzbucaqlı bir cədvəli boyamaq istəyir. Başlanğıcda, cədvəlin bütün hüceyrələri ağ rəngdədir. Hər addımda, o, bir diaqonal seçir (məsələn, 2-ci nümunəyə baxın) və həmin diaqonaldakı bütün hüceyrələri sevdiyi rəngə boyayır. Lakin bəzi diaqonalların boyanma dəyəri, uzunluğundan asılı olmayaraq, digərlərindən daha baha ola bilər. Hər bir diaqonalın boyanma dəyəri verildikdə, cədvəlin bütün hüceyrələrinin boyanmasının minimal ümumi dəyərini tapın. Qeyd etmək lazımdır ki, hüceyrələr bir neçə dəfə boyana bilər.
m sıra və n sütundan ibarət düzbucaqlı şəbəkənin 2m+2n-2 diaqonalları mövcuddur. Məsələn, əgər m = 4 və n = 3-dürsə, ümumilikdə 12 diaqonal var:
Giriş üç sətirdən ibarətdir.Birinci sətir m və n ədədlərini ehtiva edir.İkinci sətir sağa aşağıya doğru olan diaqonalların boyanma dəyərini verən m+n-1 ədədini ehtiva edir. i-ci ədəd (burada i {1,....,m+n-1}) sıra nömrəsi ilə sütun nömrəsinin fərqi i-n olan diaqonala aiddir. Beləliklə, birinci ədəd yalnız bir hüceyrədən ibarət olan diaqonala aiddir, koordinatları (0,n-1) (sıra 0, sütun n-1), ikinci ədəd (0,n-2) və (1,n-1) hüceyrələrini əhatə edən diaqonalın boyanma dəyərini təyin edir və s.Üçüncü sətir sağa yuxarıya doğru olan diaqonalların boyanma dəyərini verən m+n-1 ədədini ehtiva edir. i-ci ədəd (burada i {1,...,m+n-1}) sıra nömrəsi ilə sütun nömrəsinin cəmi i-1 olan diaqonala aiddir. Beləliklə, birinci ədəd yalnız bir hüceyrədən ibarət olan diaqonala aiddir, koordinatları (0,0), ikinci ədəd (1,0) və (0,1) hüceyrələrini əhatə edən diaqonalın boyanma dəyərini təyin edir və s.
Cədvəlin bütün hüceyrələrinin boyanmasının minimal dəyərini çıxarın.
(1 ≤ m ≤ 2 * 10^5)
(1 ≤ n ≤ 2 * 10^5)
Boyanma dəyəri - [1,10^9] intervalında tam ədədlərdir
Bu nümunədə dəyəri minimallaşdırmaq üçün aşağıdakı diaqonallar boyanmalıdır:
Hər bir bu diaqonalın boyanma dəyəri 1-dir, buna görə də yekun dəyər 4-ə bərabərdir.
Bu halda minimal dəyər aşağıdakı diaqonalların boyanması ilə əldə edilir, müvafiq olaraq dəyəri 3,2,3,3,1 və 2:
Nümunə 1
Nümunə 2