题解 P3985 【不开心的金明】

· · 题解

刚翻了下题解，发现没有我这种做法，于是就来发一下好了。

这题其实我们只用枚举下每种重量的用几个就可以了，反正总共也只有4种重量，问题不大。

同一种重量内我们当然先选价值高的了，所以读进来之后排个序就好。

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define itn int//防手滑
using namespace std;
itn n,m,w[105],v[105],ans,minn=1e9+7;
int tot0,tot1,tot2,tot3;//每种物品的个数
int w0[105],w1[105],w2[105],w3[105];//每种物品的价值
int s0[105],s1[105],s2[105],s3[105];//价值的前缀和
bool cmp(int x,int y){return x>y;}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)  scanf("%d%d",&w[i],&v[i]),minn=min(minn,w[i]);
  for(int i=1;i<=n;i++)
  {
    if(w[i]-minn==0)  w0[++tot0]=v[i];
    if(w[i]-minn==1)  w1[++tot1]=v[i];
    if(w[i]-minn==2)  w2[++tot2]=v[i];
    if(w[i]-minn==3)  w3[++tot3]=v[i];//分别放入4个数组
  }
  sort(w0+1,w0+tot0+1,cmp);
  sort(w1+1,w1+tot1+1,cmp);
  sort(w2+1,w2+tot2+1,cmp);
  sort(w3+1,w3+tot3+1,cmp);//按价值从高到底排序
  for(int i=1;i<=tot0;i++)  s0[i]=s0[i-1]+w0[i];
  for(int i=1;i<=tot1;i++)  s1[i]=s1[i-1]+w1[i];
  for(int i=1;i<=tot2;i++)  s2[i]=s2[i-1]+w2[i];
  for(int i=1;i<=tot3;i++)  s3[i]=s3[i-1]+w3[i];//计算前缀和
  for(int i=0;i<=tot0;i++)//枚举每种物品用几个
    for(int j=0;j<=tot1;j++)
      for(int k=0;k<=tot2;k++)
      {
        int sum=i*minn+j*(minn+1)+k*(minn+2);
        if(sum<=m)//不超过总钱数
        {
          int l=(m-sum)/(minn+3);
          ans=max(ans,s0[i]+s1[j]+s2[k]+s3[l]);//更新答案
        }       
      }
  printf("%d",ans);
  return 0;
}

是不是简单粗暴很好理解呢...