AOJ 0281 Formation

問題

Formation

解く

最初簡単だろうと思って、貪欲法で解いたら、WA。

DPで解こうとするとMLEになる。

適当な人数になるまではCANにしとけばいいことに気づく。

cとaが小さくなるまでCANに割り振って、そこからDP,runtime error

数分悩む。1000 1000 3とかの場合に大変なことになりそうだったので

CANにつづいてCCA、CCCに割り振る。んでメモ化再帰。

runtime errorになったので配列の大きさを調節

AC

10回以上もsubmitしてすみません。

ちゃんとアルゴリズムを考えられるようになりたい

心臓に悪いコード

int Q;
int dp[64][64][64];

int dfs(int c, int a, int n){
  if(dp[c][a][n] >= 0) return dp[c][a][n];
  int res = 0;
  if(c > 0 && a > 0 && n > 0) res = max(res, dfs(c-1, a-1, n-1)+1);
  if(c > 1 && a > 0) res = max(res, dfs(c-2, a-1, n)+1);
  if(c > 2) res = max(res, dfs(c-3, a, n)+1);
  return dp[c][a][n] = res;
}

int main(){
  cin >> Q;
  rep(i, Q){
    memset(dp, -1, sizeof(dp));
    int c, a, n;
    cin >> c >> a >> n;
    int res = 0;
    while(c > 10 && a > 5 && n > 0){
      res++;
      c--;
      a--;
      n--;
    }

    while(c > 10 && a > 5){
      res++;
      c-=2;
      a--;
    }

    while(c > 10){
      res++;
      c-=3;
    }
    res += dfs(c, a, n);
    printf("%d\n", res);
  }
  return 0;
}