注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1222][HNOI2001]产品加工  

2015-01-04 08:17:22|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一开始不会……暴力DP写到一半就会了

然后被BZOJ卡常数了QAQ

明明官方每个点给5s的

(中间还把代码交到别的题上RE了半天Q .Q)

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 6000+100;
const int P = N*5*3;
int n,m,T,ans=1e9,G = 6000*5+50;
int f[2][P];
short v[2][P];
int scan(){int i=0;scanf("%d",&i);return i;}
inline void update(int t,int j,int val){
//if(j < 0)j=-j,k^=1;
//if(j+G>P||j+G<0)printf("RE");
if(T == n){
if(val+abs(j) < ans)ans = val+abs(j);
return;
}
short &vn = v[t][j+G];
int &fn = f[t][j+G];
if(vn!=T+1){
vn = T+1;
fn = 1e9;
}
if(val < fn)fn = val;
}
int main(){
int i,j,a,b,c,i5;short t = 0;
//freopen("in.txt","r",stdin);
n = scan();
v[t][0+G] = 1;
f[t][0+G] = 0;
for(i=1;i<=n;i++){
a = scan();b = scan();c = scan();
a = -a;
T=i;i5=i*5;
for(j=0;j<=i5;j++){
//if(j+G>P||j+G<0)printf("RE");
if(v[t][j+G] == i){
int val = f[t][j+G];
if(a){
if(-a<j)update(t^1,j+a,val-a);
else update(t^1,j+a,val+j);
}
if(b)update(t^1,j+b,val);
if(c)update(t^1,j,val+c);
}
}
for(j=0;j>=-i5;j--){
//if(j+G>P||j+G<0)printf("RE");
if(v[t][j+G] == i){
int val = f[t][j+G];
if(a)update(t^1,j+a,val);
if(b){
if(b < -j)update(t^1,j+b,val+b);
else update(t^1,j+b,val-j);
}
if(c)update(t^1,j,val+c);
}
}
t^=1;
}
printf("%d\n",ans);
return 0;
}

题解:

DP

注意每个任务花的时间非常少,所以考虑是否可以用来做状态

	贪心策略: 选两个机器一起加工的物品可以一开始都放在开头,然后后面的分开做	f[i][j][k]表示	前i个物品分开做的部分在A上用时j,在B上用时k时 的最小合用时
	然后得到N^3 * 25的DP
	写出转移来发现j和k如果均>0的话,就同时减去min(j,k),并且在答案上加上min(j,k)是等价的,这状态就变成了N^2 * 10
	所以最后的时间复杂度是N^2
	注意不要用三维数组……然后就是少用maxmin函数,否则容易被卡
  评论这张
 
阅读(80)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017