0w1

CFR 321 B. Ciel and Duel ( DP )

Problem - B - Codeforces

題意:
玩遊戲王卡,對方有 N 張卡,成正面攻擊或守備狀態,如果是攻擊狀態,以攻擊力描述,守備狀態則以守備力描述。你有 M 張卡,全部都是攻擊狀態,用攻擊力描述,現在希望可以極大化對對手造成的生命值傷害總和。攻擊過的怪獸不能再進行攻擊。假設你使用的是攻擊力為 x 的怪獸,則可以攻擊攻擊狀態且攻擊力不超過 x 的對手的怪獸,攻擊後對手的怪獸會被消滅,且對對手造成 x - 對手的該怪獸攻擊力單位的生命值傷害。如果攻擊的是守備狀態的怪獸,則可以攻擊守備狀態且守備力嚴格小於 x 的怪獸,攻擊後對手的怪獸會被消滅,但不會對對手的生命值造成傷害。如果某個時間點對手沒有怪獸,那麼怪獸可以直接對對手的生命值造成自身攻擊力單位的傷害。求最大可能生命值傷害總和。

資料規模:
The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of cards Jiro and Ciel have.
Each of the next n lines contains a string position and an integer strength (0 ≤ strength ≤ 8000) — the position and strength of Jiro's current card. Position is the string "ATK" for attack, and the string "DEF" for defense.
Each of the next m lines contains an integer strength (0 ≤ strength ≤ 8000) — the strength of Ciel's current card.
TL: 2000 ms
ML: 256 MB

解法:
假設最佳解是將手邊的兩個分別具攻擊力 X, Y 的怪獸攻擊對手兩隻怪獸 A, B,且 A, B 的狀態相同,那麼若攻擊力 X ≤ Y,使得 A ≤ B,讓 X 攻擊 A,Y 攻擊 B 一定使可行的。因此考慮對三種卡片依戰鬥力升序排序後,考慮對三種卡片的張數的動態規劃。如果不能對對手生命值造成直接傷害的話,這是對的。這個動態規劃的問題在於,如果最佳解是用某些較大攻擊力的怪獸將對手的怪獸消滅後,再用攻擊力小的怪獸直接攻擊生命值,是沒辦法用這三個狀態描述。因此考慮開第四維,表示承諾會在某個時間點 ( 過去、現在、未來 ) 將對手所有怪獸消滅,如果現在的狀態是承諾的,那麼允許讓當前這隻怪獸直接攻擊生命值。最後存取答案的時候,若要存取有承諾的狀態 ( 也就是可能有進行直接攻擊的 ),那麼只能存取確實有破壞對手所有怪獸的狀態。

時間 / 空間複雜度:
O( N^2 * M )

int N, M;
vs mode; vi lp_strength;
vi fp_strength;

void init(){
  cin >> N >> M;
  mode = vs( N );
  lp_strength = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> mode[ i ] >> lp_strength[ i ];
  }
  fp_strength = vi( M );
  for( int i = 0; i < M; ++i ){
    cin >> fp_strength[ i ];
  }
}

vvvvi dp;
vi lp_atk_strength;
vi lp_def_strength;

void preprocess(){
  for( int i = 0; i < N; ++i ){
    if( mode[ i ] == "ATK" ){
      lp_atk_strength.emplace_back( lp_strength[ i ] );
    } else{
      lp_def_strength.emplace_back( lp_strength[ i ] );
    }
  }
  sort( lp_atk_strength.begin(), lp_atk_strength.end() );
  sort( lp_def_strength.begin(), lp_def_strength.end() );
  sort( fp_strength.begin(), fp_strength.end() );
  dp = vvvvi( fp_strength.size() + 1, vvvi( lp_atk_strength.size() + 1, vvi( lp_def_strength.size() + 1, vi( 2, -INF ) ) ) );
  dp[ 0 ][ 0 ][ 0 ][ 0 ] = 0;
  for( int i = 0; i < fp_strength.size(); ++i ){
    for( int j = 0; j <= lp_atk_strength.size(); ++j ){
      for( int k = 0; k <= lp_def_strength.size(); ++k ){
        for( int l = 0; l < 2; ++l ){
          upmax( dp[ i + 1 ][ j ][ k ][ l ], dp[ i ][ j ][ k ][ l ] );
          upmax( dp[ i + 1 ][ j ][ k ][ 1 ], dp[ i ][ j ][ k ][ l ] + fp_strength[ i ] );
          if( j + 1 <= lp_atk_strength.size() ){
            if( fp_strength[ i ] >= lp_atk_strength[ j ] ){
              upmax( dp[ i + 1 ][ j + 1 ][ k ][ l ], dp[ i ][ j ][ k ][ l ] + fp_strength[ i ] - lp_atk_strength[ j ] );
            }
          }
          if( k + 1 <= lp_def_strength.size() ){
            if( fp_strength[ i ] > lp_def_strength[ k ] ){
              upmax( dp[ i + 1 ][ j ][ k + 1 ][ l ], dp[ i ][ j ][ k ][ l ] );
            }
          }
        }
      }
    }
  }
}

void solve(){
  int ans = dp[ fp_strength.size() ][ lp_atk_strength.size() ][ lp_def_strength.size() ][ 1 ]; // 全部殺した
  for( int i = 0; i <= lp_atk_strength.size(); ++i ){
    for( int j = 0; j <= lp_def_strength.size(); ++j ){
      upmax( ans, dp[ fp_strength.size() ][ i ][ j ][ 0 ] );
    }
  }
  cout << ans << endl;
}