BZOJ1569: [JSOI2008]Blue Mary的职员分配(dp 暴力)

Time Limit: 15 Sec  Memory Limit: 162 MB

Submit: 483  Solved: 189

[Submit][Status][Discuss]

Description

由于Blue Mary呕心沥血的管理,Blue Mary的网络公司蒸蒸日上。现在一共拥有了n名职员,可惜没有任何的金钱和声誉。平均每名每天职员都可以给公司带来x单位金钱或者y单位声誉(名利不能双全)。并且可以花费z单位的金钱在人才交易市场发布广告招聘职员,每次发布广告三天以后就会招聘到一名职员,并且必须在发布广告并且招聘到职员的那一天才能发布下一次广告。 Blue Mary计划以最快的时间获得至少A单位金钱和至少B单位声誉,请你计算一下他至少需要多少时间才能达到他的目标。

Input

输入有且仅有一行,包含六个整数n,x,y,z,A和B,意义如题目描述所述。

Output

要求输出一行,包含一个整数,表示Blue Mary至少需要多少时间才能达到他的目标。

Sample Input

1 2 3 4 5 6

Sample Output

5

HINT

1<=n,x,y,z,A,B<=20

Source

好迷的一道题啊。。刚开始想的是二分+dp瞎搞,应该能过

但是std真的好暴力骚啊

$f[i][a][b][sta]$表示此时已经有了$i$个人,$a$点金钱,$b$点声誉,里上一次打广告过去了$sta$天

转移的时候枚举一下当前的$i$个人干什么。

对于$sta$需要分类讨论,代码里有注释

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, x, y, z, A, B; 
int f[41][21][21][4];
void Min(int &x, int y) {
    if(y < x) x = y;
}
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    N = read(); x = read(); y = read(); z = read(); A = read(); B = read();
    int ans = INF;
    memset(f, 0xf, sizeof(f));
    f[N][0][0][0] = 0;
    for(int i = N; i <= 40; i++) {
        for(int sta = 0; sta <= 3; sta++) {
            for(int a = 0; a <= max(A, z); a++) {//已经有了a的金钱 
                for(int b = 0; b <= B; b++) {//b的荣誉  
                    if(f[i][a][b][sta] < ans) {
                        int cur = f[i][a][b][sta];
                        if(a >= A && b >= B) {ans = min(ans, cur); continue;}
                        for(int pep = 0; pep <= i; pep++) {//有i个人挣钱 
                            int na = min(a + pep * x, max(A, z)), nb = min(B, b + y * (i - pep));
                            if(sta == 0) {
                                Min(f[i][na][nb][0], cur + 1);
                                if(na >= z) Min(f[i][na - z][nb][1], cur + 1);
                            }
                            //当前没有发广告,接下来可以不发广告,可以发广告 
                            else if(sta == 1 || sta == 2) Min(f[i][na][nb][sta + 1], cur + 1);
                            //当前已经发了广告,只能等着。。 
                            else {
                                Min(f[i + 1][na][nb][0], cur + 1);
                                if(na >= z) Min(f[i + 1][na - z][nb][1], cur + 1); 
                            }
                            //当前发完了广告,考虑是否继续发广告 
                        }                        
                    }
                    //    if(f[i][a][b][sta] <= 100000)printf("%d %d %d %d %d\n", i, a, b, sta, f[i][a][b][sta]);
                }    
            }            
        }

    }
    printf("%d", ans);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏noteless

抽象工厂模式 创建型 设计模式(四)

所有的ConcreteCreator的返回类型都是Product,因为抽象工厂角色Creator就是返回Product 

7020
来自专栏ACM小冰成长之路

HDU-6008-Worried School

ACM模版 描述 ? 题解 简单的模拟题,题意不是特别容易翻译,但是模拟的规则十分简单,和 WFWF 晋级资格相似,大致是一共 X+Y=GX + Y = G 个...

21380
来自专栏专知

关关的刷题日记05 —— Leetcode 219. Contains Duplicate II

关小刷刷题06 – Leetcode 219. Contains Duplicate II 题目 Given an array of integers and ...

32360
来自专栏NetCore

关于某道C#上机题的OO

前两天在园子里,有人出了一道《关于一道C#上机题的一点想法》,大概的意思呢是利用OO的思想来进行编程,接着又有一位朋友,也写了自己的答案,此朋友非常厉害,从类图...

23460
来自专栏程序员叨叨叨

8.2 函数重载

Cg 语言支持函数重载(Functon Overlaoding),其方式和 C++基本一致,通过形参列表的个数和类型来进行函数区分。例如:

12320
来自专栏专知

关关的刷题日记10——Leetcode 1. Two Sum 方法1

关小刷刷题10 – Leetcode 1. Two Sum 方法1 题目 Given an array of integers, return indices ...

31690
来自专栏小詹同学

Python系列之六——拿什么拯救你?我的大脑

我一定是智障了,话不多说,上图上图~ ? 就是这样10个选择题,你没有看错,我一定是个智障了~佩服不用穷举,也不用参考网上的大...

37740
来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

67790
来自专栏专知

【LeetCode 463】 关关的刷题日记29 Island Perimeter

关关的刷题日记29 – Leetcode 463. Island Perimeter 题目 You are given a map in form of a t...

29750
来自专栏专知

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3 方法2 方法2:遍历数组,遇到...

26290

扫码关注云+社区

领取腾讯云代金券