AOJ 0561 Books

反省

dp[i][j][l] := 今までにi冊売り、今見ているジャンルjの本をl個売った時の最大の買取価格

最初はこれでDPしようとしたが、メモリが確実に収まらないのは自明だし(それでも頑張って削減して通そうとしたが)、書いている途中でlがいらないのにも気づいて悲しくなった。[1,10)でソートしていて草が生えた。
しかし、自力でできるようになってきたのでまぁ成果はあるのかなぁ。

解法

ジャンル別で買取価格が大きい本から売るのは自明なのでソートする。
あとはDP

dp[i][j] := 今までにj冊本を売り、今、ジャンルiの本を売るときの最大の買取価格

ソースコード

vector<int> books[16];
int dp[16][2002];

int x;
int n, k, a, b;
// 今までに売った本をiとして、今見ている本のジャンルjをc個売った時の最大の買取価格
int solve(int i, int j)
{
    if(i == k)
        return 0;
    if(j > 10)
        return 0;

    if(dp[j][i] != -1)
        return dp[j][i];

    int res = 0;
    int m = 0;
    // jのジャンルの本を売らないとき
    res = solve(i, j + 1);

    int min_len = min((int)books[j].size(), k - i);
    // 売るとき
    for(int c = 0; c < min_len; c++)
    {
        m += books[j][c];
        res = max(res, solve(i + c + 1, j + 1) + m + c * (c + 1));
    }

    return dp[j][i] = res;
}

int main()
{
    for(int i = 1; i <= 10; i++)
    {
        fill(dp[i], dp[i] + 2002, -1);
    }

    cin >> n >> k;

    for(int i = 0; i < n; i++)
    {
        cin >> a >> b;
        books[b].push_back(a);
    }

    for(int i = 0; i <= 10; i++)
        sort(books[i].begin(), books[i].end(), greater<int>());

    cout << solve(0, 1) << endl;
}