4 行 4 列のチェス盤があるとしnます。すべてのセルに整数があります。それらの一部またはすべてのディスクを考えると2n、合計が最大になるように、ボード上の別のセルに配置できます。唯一の制限は、2 つのディスクを縦または横に並べることができないことです。O(n)DPを使用してボード上にディスクの最適な組み合わせを配置するにはどうすればよいですか?
1 に答える
1
第 1 に、どの列にも最大 2 つのディスクを含めることができるため、2*n を超えるディスクを使用することはできません。
d[i][mask] としましょう - 1 から i までの列をディスクで埋めた後に得られる最大量で、最後の列がマスクとして埋められます (マスクは 0000、0001、0010、0100、0101、1000、1001、または 1010 のいずれかです)。 1 はディスクが配置されたことを意味し、0 は配置されていないことを意味します)
したがって、d[i][mask1] = (d[i-1][mask2] + i 番目の列に mask1 を適用して得られる数) の最大値です。ここで、mask2 は mask1 と矛盾しない任意のマスクにすることができます。
編集 1: 何も変更する必要はありません。特定のマスクの i 番目のステップにいる場合、i-1 のマスクの回答のみに依存します。そして、あなたはすでにそれらすべてを持っています。有効なものから現在の d[i][mask] を更新しようとするだけです。すでに述べたように、d[i][mask] - 最適には、1 から i までの列を埋めるために取得できる最大値を格納し、最後の列にこのマスクの形式のディスクが含まれるようにします (i の前のマスクは関係ありません)。 -次の列に影響しないため、次の列が埋められました)
于 2015-05-20T04:19:20.590 に答える