# 11070: 【原1070】二哥的鹅

### 题目描述

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

## Input Format

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

## 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];
int pos, code_id;
linkNode(int p = 0, int q = 0): pos(p), code_id(q){}
};
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;
}
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;
for (register int i = 0; i < link_map[rest].size(); ++i)
// only keep descending order to avoid duplicate solution
else return;
}
int main() {
for (register int i = 0; i < N; ++i)
sort(code, code + N, cmp);
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