Hatena::Grouptopcoder

blu_rayの日記

2011-08-19

Codeforces Beta Round #82 Div2

| 04:31

xoxx-

A. Card Game

完全に問題文読み違えてた。

嬉々として全部で6通りとかでsubmitしてた。

B. Choosing Laptop

ループ回すだけ。

C. Buns

ボケてたので、d[i]/c[i]でソートして貪欲に…みたいな、

初めてナップサック問題に取りかかった時の様な間違いをした。

なので、ナップサックのコードでPractice通った

int n, m, a[12], b[12], c[12], d[12], dp[12][1002];

int rec(int i, int j) {
  if (dp[i][j] >= 0) return dp[i][j];
  if (i == m+1) return 0;
  int res = rec(i+1, j);
  if (j >= c[i]) {
    for(int k=1;k<=a[i]/b[i] && j-c[i]*k >= 0;k++)
      res = max(res, rec(i+1, j - c[i]*k) + d[i]*k);
  }
  return dp[i][j] = res;
}

int main(int argc, char* argv[]) {
  cin>>n>>m>>c[0]>>d[0];
  a[0] = 1000;
  b[0] = 1;
  rep(i,m) cin>>a[i+1]>>b[i+1]>>c[i+1]>>d[i+1];
  memset(dp, -1, sizeof dp);
  cout<<rec(0, n)<<endl;
  return 0;
}

DPでかけない。

D. Treasure Island

ナイーブ実装をする > 兄貴にHackされる

そのうち確認

E. Space Rescuers

問題読めない。

rate := 1411 -> 1366

順調に減少