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

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 + , INF = 1e9 + ;
inline int read() {
    char c = getchar(); int x = , f = ;
    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int N, x, y, z, A, B;
int f[][][][];
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][][][] = ;
    for(int i = N; i <= ; i++) {
        for(int sta = ; sta <= ; sta++) {
            for(int a = ; a <= max(A, z); a++) {//已经有了a的金钱
                for(int b = ; 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 = ; pep <= i; pep++) {//有i个人挣钱
                            int na = min(a + pep * x, max(A, z)), nb = min(B, b + y * (i - pep));
                            if(sta == ) {
                                Min(f[i][na][nb][], cur + );
                                if(na >= z) Min(f[i][na - z][nb][], cur + );
                            }
                            //当前没有发广告，接下来可以不发广告，可以发广告
                            else if(sta ==  || sta == ) Min(f[i][na][nb][sta + ], cur + );
                            //当前已经发了广告，只能等着。。
                            else {
                                Min(f[i + ][na][nb][], cur + );
                                if(na >= z) Min(f[i + ][na - z][nb][], cur + );
                            }
                            //当前发完了广告，考虑是否继续发广告
                        }
                    }
                    //    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);
}