1

Topcoder で dp チュートリアルを試しています。練習用に出された問題の 1 つはMiniPaint でした。私は部分的に解決策を持っていると思います-最小数を見つけてください。与えられた番号のミスペイントの。行ごとにストロークを計算し、画像全体を計算します (ナップザックの問題と同様に、dp を使用します)。ただし、最小値を計算する方法がわかりません。行ごとにいいえ。

PS私は後で一致の社説を見つけましたが、分を見つけるためのコード。番号。各行のミスペインティングが間違っているようです。誰かがコードで行ったことを正確に説明できますか?

4

2 に答える 2

0

この関数は、行をペイントするために使用できるストロークの量をstripScore()指定して、各行のミスペイントの最小数を返します。引数が正しいかどうかはわかりませんが、使用可能なストロークの量とその直前の領域の色を使用して、特定の行から開始するという考え方です。rowidstartneeded

このアルゴリズムの鍵は、k番目の領域の右側の領域の最高スコアが、必要なストロークの数と（k-1）番目の領域のペイントに使用される色によって一意に決定されることです。

于 2013-02-09T02:23:21.507 に答える