燃やす埋める練習問題１

0,1からなる文字列が与えられます。円支払うことにより、を(0ならば1に、1ならば0に)変更することができます。また、個の区間が与えられ、文字列について円追加で支払う必要があります。

• 文字列を回文にするために必要な文字の最小変更回数

例えば、110101を回文にするためには文字目を変更する必要があるためとなります。

適切にの文字を変更することにより、支払う金額を最小化してください。

入力はすべて整数である。

支払う金額の最小値を一行に出力せよ。

4 3
0011
3 3 0 9
1 4 3
2 3 0
2 4 9

6

円支払い文字目を1に変更します。となるので支払う合計金額はとなります。

5 3
10011
8 2 8 0 5
1 2 8
2 3 2
4 5 0

4

円支払い文字目を1に、円支払い文字目を0に変更します。となるので支払う合計金額はとなります。

10 10
0001011001
5 3 2 14 3 0 13 1 20 1
1 8 3
2 3 1
2 5 1
2 8 7
3 4 0
3 8 7
5 7 10
5 9 0
6 7 5
8 9 9

17