frankchenfu 的博客

frankchenfu 的博客

题解 CF176A 【Trading Business】

posted on 2018-02-20 20:07:59 | under 题解 |

这是一道比较基础的贪心题目。


首先,我们可以发现题目中的数据范围都比较小,又因为只有一次买卖,所以我们可以同时枚举起点和终点,对于每一对起点和终点做一次solve(s,t)


那么这个solve(s,t)怎么实现呢?由于确定了起点和终点,也就意味着确定了差价。这样,我们考虑买的越多一定越好,所以我们尽量每次都买尽可能多的能赚钱的东西,就是把还未尝试过的种类中,差价最大的买空为止,一直到买满$k$种或者没有差价大于$0$的产品时退出,这样一定是最优的。注意细节


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;
}