题解 CF176A 【Trading Business】
frankchenfu
2018-02-20 20:07:59
这是一道比较基础的贪心题目。
------------
首先，我们可以发现题目中的数据范围都比较小，又因为只有一次买卖，所以我们可以同时枚举起点和终点，对于每一对起点和终点做一次`solve(s,t)`。
------------
那么这个`solve(s,t)`怎么实现呢？由于确定了起点和终点，也就意味着确定了差价。这样，我们考虑买的越多一定越好，所以我们尽量每次都买尽可能多的能赚钱的东西，就是把还未尝试过的种类中，差价最大的买空为止，一直到买满$k$种或者没有差价大于$0$的产品时退出，这样一定是最优的。**注意细节**。
------------
`Cpp`代码：
```cpp
#include<cstdio>
#include<cstring>
int n,m,k;
int a[15][110],b[15][110],c[15][110];
bool vis[110];char ch[15];
int max(int x,int y){
return x>y?x:y;
}
int min(int x,int y){
return x<y?x:y;
}
int solve(int s,int t){
memset(vis,0,sizeof(vis));
int rest=k,ans=0;
while(rest>0){
bool fl=1;
int mx=-1,pos;
for(int i=1;i<=m;i++)
if(!vis[i])
if(b[t][i]-a[s][i]>mx){
fl=0;pos=i;
mx=b[t][i]-a[s][i];
}
if(fl)
break;
int num=min(rest,c[s][pos]);
rest-=num;
ans+=num*mx;
vis[pos]=1;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%s",ch);
for(int j=1;j<=m;j++)
scanf("%d%d%d",&a[i][j],&b[i][j],&c[i][j]);
}
int ans=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans=max(ans,solve(i,j));
printf("%d\n",ans);
return 0;
}
```