题目描述
王老师 最近搬家了，需要购置 a 台家电、b 件家具和 c 个装饰。他来到了商场，商场正好在举行优惠大酬宾，每家店铺都推出了一系列活动。
一共有 n=a+b+c 家店铺，活动期间在第 i 家店铺购买家电只需要 ai 元一台，购买家具只需要 bi 元一件，购买装饰只需要 ci 元一个，但每一家店铺限定每位顾客最多只能购买一种类型的物品一个。
王老师 希望在满足采购需求的情况下总花费最少，你能帮帮他求出最小花费吗？
数据范围
对于所有数据 n,a,b,c≤5000,ai,bi,ci≤109 ，保证 n=a+b+c 。
| 测试点 | 数据范围 |
|---|---|
| 1∼4 | n≤15 |
| 5∼10 | n≤100 |
| 11∼14 | c=0 |
| 15∼20 | 无限制 |
首先根据题面不难想到定义dp[i][j][k]（表示经过i家店铺，买j台家电，k件家具，n-j-k个装饰的最小花费），但只能过%50分。
考虑优化：我们可以利用贪心来优化dp[i][j]表示考虑了1到i家店，选了j个装饰的最小费用，那么剩下i-j个物品就会按照贪心策略优先买购买家具，然后购买家电。
按b[i]-a[i]排序，便有以下转移方程
若i-j<=B f[i][j]=min(f[i-1][j-1]+c[i],f[i-1][j]+b[i])
否则：f[i][j]=min(f[i-1][j-1]+c[i],f[i-1][j]+a[i]);
代码：
#include <bits/stdc++.h>using namespace std;
#define int long long
int f[5005][5005],n,a,b,c;
struct node{
int a,b,c;
}s[5005];
bool cmp(node x,node y){
return x.b-x.a<y.b-y.a;
}
signed main(){
freopen("buy.in","r",stdin);
freopen("buy.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a>>b>>c;
for(int i=1;i<=n;i++)cin>>s[i].a>>s[i].b>>s[i].c;
sort(s+1,s+n+1,cmp);
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=min(i,c);j++){
if(i-j<=b)f[i][j]=f[i-1][j]+s[i].b;
else f[i][j]=f[i-1][j]+s[i].a;
if(j!=0)f[i][j]=min(f[i][j],f[i-1][j-1]+s[i].c);
}
cout<<f[n][c];
return 0;
}
总结：T4在考场上写了个记忆化搜索，但是状态写错了，以至于与爆搜的20分都没拿到。。而且即便大样例过了，也有可能爆0，所以不能过度依赖大样例，需要自己造hack数据。 标签：赛道,node,5005,2024.8,T4,int,购买,店铺 From： https://www.cnblogs.com/qianqian2022/p/18391123