RQNOJ 624 运动鞋：dp

题目链接：https://www.rqnoj.cn/problem/624

题意：

　　小明有奖学金啦！所以他要去买运动鞋。

　　总共有n款鞋，分别属于t个品牌。

　　每款鞋的价格为c[i]，在小明心目中的价值为w[i]。

　　小明只有m元的奖学金。

　　小明同学有强迫症，每个品牌都要至少买一双，并且同一款不会买两双。

　　问你所买的鞋在小明心目中的价值之和最大为多少。

题解：

　　表示状态：

　　　　dp[i][j][k][p] = max value

　　　　i：考虑到第i个品牌

　　　　j：考虑到第i个品牌中的第j款鞋

　　　　k：当前花费

　　　　p：第i个品牌是否至少买了一双 (p == 0 / 1)

　　找出答案：

　　　　max dp[t][0][k][0]　(0<=k<=m)

　　　　考虑到第t个品牌（不存在）的第一双鞋。

　　如何转移：

　　　　now: dp[i][j][k][p]

　　　　三种决策：

　　　　　　（1）买当前的鞋，接下来考虑当前品牌的下一款鞋　　（买）

　　　　　　（2）不买当前的鞋，接下来考虑当前品牌的下一款鞋　（不买）

　　　　　　（3）买当前的鞋，接下来考虑下一个品牌的第一款鞋　（下个品牌）

　　　　对应方程：

　　　　　　dp[i][j+1][k+c[i][j]][1] = dp[i][j][k][p] + w[i][j]

　　　　　　dp[i][j+1][k][p] = dp[i][j][k][p]

　　　　　　dp[i+1][0][k][0] = dp[i][j][k][1]

　　边界条件：

　　　　dp[0][0][0][0] = 0

　　　　others = -1

AC Code:

 1 // state expression:
 2 // dp[i][j][k][p] = max value
 3 // i: considering ith brand
 4 // j: considering jth shoes
 5 // k: present cost
 6 // p: whether ith brand has been boungth (p == 0/1)
 7 //
 8 // find the answer:
 9 // max dp[t][0][k][0]
10 //
11 // transferring:
12 // now: dp[i][j][k][p]
13 // dp[i][j+1][k+c[i][j]][1] = dp[i][j][k][p] + w[i][j]
14 // dp[i][j+1][k][p] = dp[i][j][k][p]
15 // dp[i+1][0][k][0] = dp[i][j][k][1]
16 //
17 // boundary:
18 // dp[0][0][0][0] = 0
19 #include <iostream>
20 #include <stdio.h>
21 #include <string.h>
22 #define MAX_N 105
23 #define MAX_T 15
24 #define MAX_C 10005
25 
26 using namespace std;
27 
28 int n,m,t;
29 int x,y,z;
30 int ans;
31 int dp[MAX_T][MAX_N][MAX_C][2];
32 int cnt[MAX_T];
33 int c[MAX_T][MAX_N];
34 int w[MAX_T][MAX_N];
35 
36 void read()
37 {
38     memset(cnt,0,sizeof(cnt));
39     cin>>n>>m>>t;
40     for(int i=0;i<n;i++)
41     {
42         cin>>x>>y>>z;
43         c[x][cnt[x]]=y;
44         w[x][cnt[x]]=z;
45         cnt[x]++;
46     }
47 }
48 
49 void solve()
50 {
51     ans=-1;
52     memset(dp,-1,sizeof(dp));
53     dp[1][0][0][0]=0;
54     for(int i=1;i<=t;i++)
55     {
56         for(int j=0;j<=cnt[i];j++)
57         {
58             for(int k=0;k<=m;k++)
59             {
60                 for(int p=0;p<2;p++)
61                 {
62                     if(dp[i][j][k][p]!=-1)
63                     {
64                         if(k+c[i][j]<=m && j+1<=cnt[i])
65                         {
66                             dp[i][j+1][k+c[i][j]][1]=max(dp[i][j+1][k+c[i][j]][1],dp[i][j][k][p]+w[i][j]);
67                         }
68                         if(j+1<=cnt[i])
69                         {
70                             dp[i][j+1][k][p]=max(dp[i][j+1][k][p],dp[i][j][k][p]);
71                         }
72                         dp[i+1][0][k][0]=max(dp[i+1][0][k][0],dp[i][j][k][1]);
73                     }
74                 }
75             }
76         }
77     }
78     for(int j=0;j<=m;j++)
79     {
80         ans=max(ans,dp[t+1][0][j][0]);
81     }
82 }
83 
84 void print()
85 {
86     if(ans==-1) cout<<"Impossible"<<endl;
87     else cout<<ans<<endl;
88 }
89 
90 int main()
91 {
92     read();
93     solve();
94     print();
95 }