Skip to content

11070: 【原1070】二哥的鹅

题目

题目描述

author: duruofei 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1070

Description

鹅,鹅,鹅,

曲项向天歌。

白毛浮绿水,

红掌拨清波。

首句连用三个“鹅”字,表达了二哥对鹅十分喜爱之情。这三个“鹅”字,可以理解为二哥听到鹅叫了三声,也可以理解为二哥看到鹅在水中嬉戏,十分欣喜,高兴地连呼三声“鹅、鹅、鹅”。二哥如此喜欢鹅,也养了很多鹅,准确的说,二哥养了 K 只鹅。

有趣的是,这 K 只鹅每只每天要吃总计 V 行的 code,一行不能多,一行不能少,否则就会“鹅鹅鹅”地叫。

几年下来,经历了Tiger, Mips, Nachos, Fatworm, Tenet等等之后,二哥积攒了 N 种 code 可以喂鹅,第 i 种 code 有固定的行数 V[i] 和营养价值 W[i]。

然而,这 K 只鹅的脾气十分古怪,它们中的某一只一旦发现自己吃的 V 行 code 和别的鹅吃的完全相同也会“鹅鹅鹅”地叫;一旦发现相同种类的 code 自己吃了两次也会“鹅鹅鹅”地叫。

二哥为了让所有鹅能吃到营养价值总和最多的 code 且不让任一只“鹅鹅鹅”地叫,很伤脑筋。聪明的你,能帮帮他吗?

Input Format

第一行有三个整数 K、V、N 分别表示二哥养的鹅的数量、每只鹅每天的食量、二哥拥有的 code 种类。

第二行开始到 N+1 行,每行两个整数,分别代表二哥拥有的一种 code 的行数和营养价值。

(具有相同行数和价值的 code 也是不同种类)

Output Format

输出仅一行,仅含一个整数,表示在不出现“鹅鹅鹅”的情况下,二哥每天喂给鹅们的 code 的最大总营养价值。

Hint

数据范围:

对于70分的数据,二哥养了不超过10只鹅,每只鹅的食量不超过1200行,code不超过100种。

对于95分的数据,二哥养了不超过50只鹅,每只鹅的食量不超过5000行,code不超过200种。任何正整数不超过5000。

对于100分的数据,二哥养了不超过70只鹅,每只鹅的食量不超过6000行,code不超过300种,最后结果不超过2^31-1。

样例说明: 一种可以得到最大总价值的喂鹅方案是:第一只鹅吃行数为7、2、1的code,价值为25。第二只鹅吃行数为3、7的code,价值为32。总价值为57。两只鹅都喂饱了,且没有“鹅鹅鹅”~

Sample Input

2 10 5
3 12
7 20
2 4
5 6
1 1

Sample Output

57

FineArtz's solution

/* 二哥的鹅 */
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 2147483647;

int k, V, n;
int v[305], w[305];
int f[6001][72];
int t1[72], t2[72];

int main(){
    cin >> k >> V >> n;
    for (int i = 1; i <= n; ++i)
        cin >> v[i] >> w[i];
    for (int i = 0; i <= V; ++i)
        for (int j = 0; j <= k; ++j)
            f[i][j] = -INF;
    f[0][1] = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = V; j >= v[i]; --j){
            for (int l = 1; l <= k; ++l){
                t1[l] = f[j - v[i]][l] + w[i];
                t2[l] = f[j][l];
            }
            int x = 1, y = 1;
            for (int z = 1; z <= k; ++z){
                if (t1[x] > t2[y])
                    f[j][z] = t1[x++];
                else
                    f[j][z] = t2[y++];
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= k; ++i){
        ans += f[V][i];
    }
    cout << ans << endl;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX_V 6010
#define MAX_N 305
using namespace std;
int K, V, N, ans;
struct Node {
    int weight, value;
    Node(int p = 0, int q = 0): weight(p), value(q) {} 
} code[MAX_N];
struct linkNode {
    int pos, code_id;
    linkNode(int p = 0, int q = 0): pos(p), code_id(q){}
};
vector<linkNode> link_map[MAX_V];
int cur_max_value[MAX_V];
priority_queue<int, vector<int>, greater<int> > q;
bool has_k_solution;
inline bool cmp(const Node &p, const Node &q) {
    // return p.weight != q.weight ? p.weight > q.weight : p.value > q.value;
    return p.value > q.value;
}
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    // if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    // return res * flag;
    return res;
}
void calc(int rest, int cur_value, int pre_code_id) {
    // find a solution
    if (!rest) {
        // number of saved solutions is less than K
        if (!has_k_solution) {
            q.push(cur_value);
            if (q.size() == K) has_k_solution = true;
        }
        else if (cur_value > q.top()) {// better than current worst solution
            q.pop(); q.push(cur_value);
        }
        return;
    }
    // worse than current worst solution saved in queue
    if (has_k_solution && cur_max_value[rest] + cur_value <= q.top()) return;
    // find links to zero
    for (register int i = 0; i < link_map[rest].size(); ++i)
        // only keep descending order to avoid duplicate solution
        if (link_map[rest][i].code_id < pre_code_id)
            calc(link_map[rest][i].pos, cur_value + code[link_map[rest][i].code_id].value, link_map[rest][i].code_id);
        else return;
}
int main() {
    K = read(), V = read(), N = read();
    for (register int i = 0; i < N; ++i)
        code[i].weight = read(), code[i].value = read();
    sort(code, code + N, cmp);
    // init link list
    link_map[0].push_back(linkNode(-1, -1));
    // create link map
    for (register int i = 0; i < N; ++i)
        for (register int j = V; j >= code[i].weight; --j)
            // if j can be reached from j - code[i].weight by i-th code
            if (!link_map[j - code[i].weight].empty()) {
                link_map[j].push_back(linkNode(j - code[i].weight, i));
                cur_max_value[j] = max(cur_max_value[j], cur_max_value[j - code[i].weight] + code[i].value);
            }
    calc(V, 0, MAX_N);
    while (!q.empty()) {
        ans += q.top(); q.pop();
    }
    printf("%d\n", ans);
    return 0;
}