1.1 题目背景
铜企鹅是企鹅餐馆的老板，他正在计划如何使得自己本年度收益增加。
1.2 题目描述
共有n 种食材，一份食材i 需要花 \(t_i\) 小时不间断地进行播种，施肥，直至收获。当然，一份食材i 是可以直接卖掉得到 \(w_i\) 块钱的。
招牌菜共有m 种，一份招牌菜i 需要消耗一定的食材，花 \(T_i\) 小时不间断地来烹饪，叫卖，并最终卖出得到 \(W_i\) 块钱。 整个季度换算下来一共有\(T_{max}\) 小时可供你使用，铜企鹅需要在这期间赚到最多的钱，1.3 格式
1.3.1 输入格式
第一行一个整数T，表示数据组数。
一行三个整数n; m; \(T_{max}\)，含义如题所示。 接下来n行，每行两个整数 \(t_i\) ; \(w_i\)，含义如题所示。 接下来m行，每行两个整数 \(T_i\) ; \(W_i\)，含义如题所示。 接下来m行，每行n 个整数，第j 个数 \(d_j\)表示当前招牌菜需要 \(d_j\) 个食材j。1.3.2 输出格式
对于每组数据，输出一行一个整数，表示你所能赚到的最多的钱。
1.4 样例
1.4.1 样例输入
3
1 1 48 2 2000 9 21864 54 4 46 17 52 4 36 5 43 16 62 9 31659 1 20431 4 623 1 11961 4 5 3 5 5 4 3 4 3 3 3 3 4 4 5 5 10 0 48 10 41 18 48 2 14 22 65 12 77 7 48 4 85 2 61 24 85 8 34
1.4.2 样例输出
53728
410 1464
1.5 数据范围
| Subtask | 分值 | n | m | T |
|---|---|---|---|---|
| 1 | 3 | 1 | 1 | 0 |
| 2 | 20 | 1 | 1 | 5 |
| 3 | 10 | 4 | 4 | 5 |
| 4 | 17 | 2000 | 0 | 5 |
| 5 | 50 | 2000 | 2000 | 4 |
对于100% 的数据，保证0 < t_i ; T_i T_max 5000; 0 w_i;W_i 109，
每份招牌菜使用的食材的个数总数不超过10^5。第一眼以为是树形dp（最近做多了...）写完后面的暴力回来先写了subtask4的完全背包，然后就发现较高级的物品和基础物品没啥区别。。直接把对应的原材料所需时间加到高级物品上就好了
#include#include #include using namespace std;long long wei[4001],dp[5001],va[4001];long long read() { int ret=0; char c; c=getchar(); while(c>'9'||c<'0') { c=getchar(); } while(c>='0'&&c<='9') { ret=ret*10+c-'0'; c=getchar(); } return ret;}int main() { long long t; t=read(); while(t--) { long long n,m,T; n=read(); m=read(); T=read(); memset(wei,0,sizeof(wei)); memset(dp,0,sizeof(dp)); memset(va,0,sizeof(va)); for(int i=1; i<=n; i++) { wei[i]=read(); va[i]=read(); } for(int i=1; i<=m; i++) { wei[n+i]=read(); va[n+i]=read(); } for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { int x; x=read(); wei[n+i]+=x*wei[j]; } } for(int i=1; i<=n+m; i++) { for(int j=wei[i]; j<=T; j++) { dp[j]=max(dp[j],dp[j-wei[i]]+va[i]); } } printf("%lld\n",dp[T]); } return 0;}