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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1226][SDOI2009][DP]学校食堂Dining  

2014-08-06 13:03:00|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@BZOJ1226: [SDOI2009]学校食堂Dining

蛋疼的DP题

先上代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
const int N = 1000+1;
const int MAX = 1000000000;
using namespace std;
int n,m,kw[N],rs[N];
int f[N][128*2+10][20],two[40],ans[N],left[N][128*2+10];
bool v[N][128*2+10][20];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
struct zt{
int i,j,k;
zt(int ii,int jj,int kk):i(ii),j(jj),k(kk){}
};queue<zt>dui;
void update(int i,int j,int k,int cost){

while(j&1){j/=2;i++;k--;}
if(cost<f[i][j][k]){
f[i][j][k]=cost;
if(!v[i][j][k]&&i<n){
dui.push(zt(i,j,k));
v[i][j][k]=1;
}
}
}
int getleft(int i,int x){
if(left[i][x]) return left[i][x];
int l,j;x/=2;
for(l=rs[i+1],j=1;l&&i+1+j<=n;l--,j++,x/=2)
if((x&1)==0)l=min(l,rs[i+1+j]+1); //&的优先级异常低
return left[i][x]=j;
}
int main(){
//freopen("input.txt","r",stdin);
//最后一个问题:少压一位状态
int i,j,nn,k,l,kk;
nn=scan();
for(two[0]=1,i=1;i<=30;i++) two[i]=two[i-1]*2;
for(int ii=1;ii<=nn;ii++){
n=scan();
for(i=1;i<=n;i++)
{kw[i]=scan();rs[i]=scan();}
for(i=0;i<=n;i++)
for(j=0;j<=two[8];j++){
left[i][j]=0;
for(k=0;k<=15;k++)
f[i][j][k]=MAX,v[i][j][k]=0;
}
f[0][0][7]=0;v[0][0][7]=1;
//DP
//写了一坨之后发现必须要Bfs
//又发现已经领到饭的同学就不用管忍耐度了
dui.push(zt(0,0,7));
while(!dui.empty()){
zt now = dui.front();dui.pop();
i=now.i;j=now.j;k=now.k;
int lef=getleft(i,j);
for(kk=1;kk<=lef;kk++)
if((two[kk-1]&j) == 0){
if(i==0&&j==0) update(i,j|two[kk-1],kk+7,0);
else update(i,j|two[kk-1],kk+7,
f[i][j][k]+((kw[i+(k-7)] | kw[i+kk])-(kw[i+(k-7)] & kw[i+kk])));
}
}
i=n;j=0;ans[n]=MAX;
for(k=0;k<=7;k++)
if(f[n][0][k]<ans[n])//i打成n -> 40min
ans[n]=f[n][0][k];
printf("%d\n",ans[n]);
}
return 0;
}

题解:

状压DP,但是有各种细节需要注意

状态:f[i][j][k]

表示前i个同学都已经领到饭,第i个同学后面几个同学的领饭情况是j(二进制),最后一个领饭同学的位置为k

这时所用的最少时间就是f[i][j][k]

因为同学的最大忍受度是7

所以最后一个领饭的同学只可能在i-7 ~ i+8

后面同学的领饭情况也只需要压8位


f数组的大小只需要f[N][2^8][16]

然后自己YY一下怎么转移就好了


虽然看起来不太难但是实际上有很多细节需要注意:

①后面同学情况j不能从小到大枚举,可以用记忆化的bfs解决

②当一个同学已经领到饭的时候,他的忍耐度就可以忽略了

③后面同学的领饭情况需要压8位而不是7位

④注意位运算的优先级,比 == 还要低


我昨晚上调到1:00还没调出来QAQ

然后今天早上在去机房的路上突然想起来状态少压一位/A\

【人生一大错觉:这道题很简单我马上就能调出来了】


最近参加了各种比赛&测试没写总结恩……

但是还有好多事要做

等做完了回来补上总结

  评论这张
 
阅读(100)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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