BZOJ1569: [JSOI2008]Blue Mary的职员分配(dp 暴…
2018-06-27 09:42:39来源:博客园 阅读 ()
Submit: 483 Solved: 189
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
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 + 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); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- [JSOI2008][BZOJ1012] 最大数(动态开点线段树) 2018-06-17
- P1198 [JSOI2008]最大数 2018-06-17
- P1197 [JSOI2008]星球大战 2018-06-17
- BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash