1.1 题目背景
铜企鹅是企鹅餐馆的老板，他正在计划如何使得自己本年度收益增加。
1.2 题目描述
共有n 种食材，一份食材i 需要花 (t_i) 小时不间断地进行播种，施肥，直至收获。当然，一份食材i 是可以直接卖掉得到 (w_i) 块钱的。
招牌菜共有m 种，一份招牌菜i 需要消耗一定的食材，花 (T_i) 小时不间断地来烹饪，叫卖，并最终卖出得到 (W_i) 块钱。
整个季度换算下来一共有(T_{max}) 小时可供你使用，铜企鹅需要在这期间赚到最多的钱，这样他才有足够多的钱来steam 剁手，或者氪金手游。
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<cstdio>
#include<cstring>
#include<algorithm>
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
",dp[T]);
}
return 0;
}