AOJ : 2219 - THE BYDOLM@STER

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2219&lang=jp
日本語なので省略です.
アイマス！

アルゴリズム

各能力値を別々に考えて, 動的計画法によって最大合計値を求めます.
そうすると, ボーカル, ダンス, ルックスのそれぞれの最大合計値が出ます.
あとは, その中の最大値が, ユニットのランク最大値となります.
メモ化＋再帰でやってます.

プログラム

#include <iostream>
#include <cstring>
using namespace std;

int n,m;
int c[301],v[301],d[301],l[301];
int dp[301][301];

int solve(int idx,int rem,int *t){
  if(idx == n) return 0;
  if(dp[idx][rem] != -1) return dp[idx][rem];
  int res = 0;
  for(int i=0;i*c[idx]<=rem;i++){
    res = max(res,i*t[idx]+solve(idx+1,rem-i*c[idx],t));
  }
  return dp[idx][rem]=res;
}

int main(void){
  while(cin>>n>>m){
    for(int i=0;i<n;i++){
      char ch = getchar();
      while((ch=getchar()) != '\n');
      cin>>c[i]>>v[i]>>d[i]>>l[i];
    }

    int ans = 0;
    memset(dp,-1,sizeof(dp));
    ans = max(ans,solve(0,m,v));
    memset(dp,-1,sizeof(dp));
    ans = max(ans,solve(0,m,d));
    memset(dp,-1,sizeof(dp));
    ans = max(ans,solve(0,m,l));
    cout<<ans<<endl;
  }

  return 0;
}