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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1296][SCOI2009]粉刷匠  

2014-10-20 09:54:12|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
看着会T,写完测了一下会T交上去A了……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
//#include<ctime>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
int n,m,t,f[52][51][2501],sum[51][51];
int main(){
//int start = clock();
//freopen("in.txt","r",stdin);
int i,j,k,l;char cc;
n = scan();m = scan();t = scan();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
sum[i][j] = sum[i][j-1];
if(cc=='1')sum[i][j]++;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
int sj = sum[i][j];
for(k=1;k<=t;k++){
int &now = f[i][j][k],tmp;
now = f[i][j-1][k];
for(l = 0;l<j;l++){
tmp = sj - sum[i][l];
tmp = max(j-l - tmp,tmp) + f[i][l][k-1];
if(tmp > now)now = tmp;
}
//if(!now)break;
}
if(j==m)
for(k=1;k<=t;k++)
f[i+1][0][k] = f[i][m][k];
}
printf("%d\n",f[n+1][0][t]);
//printf("%f",(clock() - start)/1000.0);
return 0;
}

题解:
DP
f[i][j][k]表第i行涂到第j个格子,用了k次所得到的价值。
然后暴力枚举本行的转移就行了。
但是明显最大数据会T……
1.x~2.x s
所以我感觉不是标解……为了骗分又写了一个寻址优化版本

#include<cstdio>
#include<cstdlib>
//#include<ctime>
#include<algorithm>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
int n,m,t,f[52][51][2501],sum[51][51];
int main(){
//int start = clock();
//freopen("in.txt","r",stdin);
int i,j,k,l;char cc;
n = scan();m = scan();t = scan();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
sum[i][j] = sum[i][j-1];
if(cc=='1')sum[i][j]++;
}
int ai,aj,ak,am;
ai = &f[1][0][0] - &f[0][0][0];
aj = &f[0][1][0] - &f[0][0][0];
ak = &f[0][0][1] - &f[0][0][0];
am = &f[0][m][0] - &f[0][0][0];
int *fi,*fij,*fijk;
fi = &f[1][0][0];
for(i=1;i<=n;i++,fi+=ai)
for(j=1,fij=fi+aj;j<=m;j++,fij+=aj){
int sj = sum[i][j];
for(k=1,fijk=fij+ak;k<=t;k++,fijk+=ak){
int &now = *fijk,tmp, *filk;
//now = f[i][j-1][k];
now = *(fijk-aj);
for(l = j-1,filk = fijk-ak-aj;l>=0;l--,filk-=aj){
tmp = sj - sum[i][l];
tmp = max(j-l - tmp,tmp) + *filk;
if(tmp > now)now = tmp;
}
if(!now)break;
}
int *fijk,*fimk;
fijk = fi+ai+ak;
fimk = fi+am+ak;
if(j==m)
for(k=1;k<=t;k++,fijk+=ak,fimk+=ak){
f[i+1][0][k] = f[i][m][k];
}
}
printf("%d\n",f[n+1][0][t]);
//printf("%f",(clock() - start)/1000.0);
return 0;
}

然后比较好的机子还是要跑1.0几秒(还是会T……)
我到网上搜了一下题解,发现有位神犇的题解里是这么说的:
 看题解发现还有一个前缀和优化,可以每次转移达到O(1),a[i]表示1..i有几个1就OK了,加上这个优化时间缩成了1/3.
没有给出代码和详细说明我也不太清楚究竟是什么,不过已经通过评论问他了
Update[2014-11-30]:
那位神犇的做法其实和我差不多
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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