自动搬运

查看原文

来自洛谷，原作者为

	attack **

搬运于2025-08-24 21:59:46，当前版本为作者最后更新于2018-06-25 20:19:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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