51Nod 1548 欧姆诺姆和糖果

Problem

一天，欧姆诺诺姆来到了朋友家里，他发现了许多糖果。有蓝色和红色两种。他知道每颗红色糖果重Wr克，每颗蓝色糖果重Wb克。吃一颗蓝色糖果会给他带来Hb的欢乐值，吃一颗红色糖果会给他带来Hr的欢乐值。

欧姆诺姆最多只能吃C克的糖果，而且每一颗糖果不能只吃一半。现在他想通过吃蓝色和红色的糖果来获得最大的欢乐值。

样例解释：每一种糖果吃两颗即可。

Solution

我是水过去的，直接全选单位价值最高的，然后向下枚举。

证明见解题报告。

Code

#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<string.h>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll w[10],h[10];
ll c;
int main() {
    io_opt;
    cin>>c>>h[1]>>h[2]>>w[1]>>w[2];
    db x1=(db)h[1]/w[1],x2=(db)h[2]/w[2];
    if(x1<x2){
        swap(h[1],h[2]);
        swap(w[1],w[2]);
    }
    ll x=c/w[1],y=(c-x*w[1])/w[2];
    ll ans=x*h[1]+y*h[2];
    for(int i=1;i<=100000&&x-i>=0;i++){
        ll xx=x-i,yy=(c-xx*w[1])/w[2];
        ans=max(ans,xx*h[1]+yy*h[2]);
    }
    cout<<ans<<endl;
    return 0;
}