Problem Statement
一家商店里有 $N$ 种商品出售。 $i$ （件）产品的价格为 $P_i$ 日元，效用值为 $U_i$ ，颜色为 $C_i$ 。
你将从这些 $N$ 产品中选择一个子集购买（可能一个都不）。所选商品的总价最多为 $X$ 日元。
您的满意度为 $S + T \times K$ ，其中 $S$ 是所选产品的效用总和， $T$ 是所选产品中不同颜色的数量。这里， $K$ 是一个给定的常数。
您选择的产品将使您的满意度最大化。求最大满意度。
Constraints
- $1 \leq N \leq 500$
- $1 \leq X \leq 50000$
- $1 \leq K \leq 10^9$
- $1 \leq P_i \leq X$ $(1 \leq i \leq N)$
- $1 \leq U_i \leq 10^9$ $(1 \leq i \leq N)$
- $1 \leq C_i \leq N$ $(1 \leq i \leq N)$
- All input values are integers.
The input is given from Standard Input in the following format:
$N$ $X$ $K$
$P_1$ $U_1$ $C_1$
$P_2$ $U_2$ $C_2$
$\vdots$
$P_N$ $U_N$ $C_N$
Output
Print the answer.
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
const int N = 505;
const int M = 5e4+100;
struct node
{
int cost,val,color;
bool operator<(const node &another) const
{
return color < another.color;
}
}arr[N];
int dp[N][M];//在第i件商品下有j元的情况下最多可以获得多少满意度
int n,m,k;
void solve()
{
cin >> n >> m >> k;
for(int i=1;i<=n;i++)
{
cin >> arr[i].cost >> arr[i].val >> arr[i].color;
}
sort(arr+1,arr+1+n);
for(int i=1,ptr=0;i<=n;i++)
{
// case 1 : 当前的钱不足以购买此商品 此时状态不变即还等于遍历到上个物品时的状态 dp[i][j] = dp[i-1][j]
for(int j=1;j<arr[i].cost;j++)
{
dp[i][j] = dp[i-1][j];
}
// case 2 : 当前的钱可以购买此商品 需要在 不买(A) 买(B) 和 买一个新颜色的物件(C)
for(int j=arr[i].cost;j<=m;j++)
{
dp[i][j] = max(
{
dp[i-1][j],// choice A
dp[i-1][j-arr[i].cost] + arr[i].val,// choice B
dp[ptr][j-arr[i].cost] + arr[i].val + k// choice C
//每多一个颜色种类加一个K
// 从上一个颜色的最后一个物品转移过来
// 保证当前物品此时是当前颜色中第一个取的
}
);
}
//更新ptr
if(arr[i].color!=arr[i+1].color)
{
ptr = i; // ptr表示上一个颜色的最后一个商品的位置。
}
}
cout << dp[n][m];
}
|