状態圧縮問題

2178 ワード
D-格子取数(1)
Time Limit:5000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit 
Status
Description
n*nの格子の碁盤をあげて、各格子の中に非負の数があります. 
任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
Input
複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
Output
各テストインスタンスについて、取得可能な最大和を出力します.
Sample Input 
3
75 15 21 
75 15 28 
34 70 5

Sample Output 
188

コード:

H:デート

    • を表示
  • 提出
  • 統計
  • 質問
    • 合計時間制限:
    2000ms 
    メモリの制限:
    65535kB
    説明
    あるacmerは妹とデートしたいと思っています.彼らはN行M列の四角い地図の中にいます.acmerは地図の左上の角座標が(1,1)の位置にあり、妹は地図の右下の角座標が(n,m)の位置にあり、acmerは1単位時間で上下左右に隣接する格子に移動することができます.しかし、この地図には壁と異なる色のドアがたくさんあります.壁は通り抜けられません.ドアの色と同じ鍵を手に入れてこそ、対応する色のドアを開けることができます.2つの格子の間のドアがacmerを開けてこそ、現在の格子からドアの反対側の格子まで歩くことができます.acmerはもちろん一番早く妹の位置に着きたいのですが、acmerが一番短い到着時間を計算するのに役立ちますか?
    入力
    複数のテストデータ.
    1行目は、地図にN行M列、P色のゲート(1<=N、M<=50、0<=P<=10)があることを示す3つの整数を入力します.
    2行目には、壁とドアの数が合計K個であることを示す整数Kが入力される(0<=K<=500).
    次のK行は、行ごとに5つの整数、xi 1、yi 1、xi 2、yi 2、giを入力します.gi値が0の場合、格子(xi 1,yi 1)と格子(xi 2,yi 2)の間に壁があり、gi>=1の場合、格子(xi 1,yi 1)と格子(xi 2,yi 2)の間にgi色のドアがあることを示します.
    次に、Sの数の鍵が迷路にあることを示す整数Sを入力する(0<=S<=50)
    次にS行は、行ごとに3つの整数、xi 1、yi 1、qiを入力し、格子(xi 1、yi 1)がqiの色を持つ鍵を含むことを示す.
    1 <= xi1,xi2 <= N 1 <= yi1,yi2 <= M | xi1 - xi2 | + | yi1 - yi2 |=1 0 <= gi <= P 1 <= qi <= P
    しゅつりょく
    出力整数は、acmerが最も短い妹の位置に到達した時間を表し、acmerが妹の位置に到達できない場合は「zhuding gudu yisheng」を出力します(引用符は出力しません).
    サンプル入力
    4 4 9
    9
    1 2 1 3 2
    1 2 2 2 0
    2 1 2 2 0
    2 1 3 1 0
    2 3 3 3 0
    2 4 3 4 1
    3 2 3 3 0
    3 3 4 3 0
    4 3 4 4 0
    2
    2 1 2
    4 2 1

    サンプル出力
    14
    • を表示
  • 提出
  • 統計
  • 質問
    • コード:
    MVCモード
    iperf使用概要