BZOJ2828 : 火柴游戏
2023-09-11 14:15:04 时间
设$f[i][j][k]$表示考虑了前$i$个数字,增加了$j$根火柴,删掉了$k$根火柴是否可能,用bitset加速DP。
然后设$g[i][j]$表示增加了$i$根火柴,删掉了$j$根火柴的最小代价,枚举移动次数进行更新。
决策满足单调性,故可以分治求解。
设$m=14n$,则时间复杂度为$O(\frac{nm^2}{64}+m^2\log m)$。
#include<cstdio> #include<bitset> using namespace std; const int N=205,M=2810,inf=~0U>>1; int n,m,p1,q1,p2,q2,p3,q3,i,j,k,o,w1[M],w2[M],w3[M],g[M],ans=inf; int S[10]={126,48,107,121,53,93,95,112,127,125},dx[10][10],dy[10][10]; char a[N],b[N]; bitset<M>f[2][M]; inline void up(int&a,int b){if(a>b)a=b;} void solve(int l,int r,int dl,int dr){ int m=(l+r)>>1,dm=dl,&t=g[m]; for(int o=dl;o<=m&&o<=dr;o++){ int tmp=w1[i-o]+w2[m-o]+w3[o]; if(tmp<t)t=tmp,dm=o; } if(l<m)solve(l,m-1,dl,dm); if(r>m)solve(m+1,r,dm,dr); } int main(){ scanf("%d%s%s%d%d%d%d%d%d",&n,a+1,b+1,&p1,&q1,&p2,&q2,&p3,&q3); for(i=1;i<=n;i++)a[i]-='0',b[i]-='0'; m=n*14; for(i=1;i<=m;i++)w1[i]=w1[i-1]+p1*i+q1,w2[i]=w2[i-1]+p2*i+q2,w3[i]=w3[i-1]+p3*i+q3; for(i=0;i<10;i++)for(j=0;j<10;j++)for(k=0;k<7;k++){ if(!(S[i]>>k&1)&&(S[j]>>k&1))dx[i][j]++; if((S[i]>>k&1)&&!(S[j]>>k&1))dy[i][j]++; } f[0][0][0]=1; for(i=o=1;i<=n;i++,o^=1){ for(j=0;j<=i*14;j++)f[o][j].reset(); for(j=0;j<=(i-1)*14;j++)for(k=0;k<10;k++) f[o][j+dx[a[i]][k]+dx[b[i]][k]]|=f[o^1][j]<<(dy[a[i]][k]+dy[b[i]][k]); } for(i=0;i<=m;i++){ for(j=0;j<=m;j++)g[j]=inf; solve(0,m,0,i); for(j=0;j<=m;j++)if(f[o^1][i][j])up(ans,g[j]); } return printf("%d",ans),0; }
相关文章
- Cocos2D将v1.0的tileMap游戏转换到v3.4中一例(二)
- (NO.00001)iOS游戏SpeedBoy Lite成形记(十五)
- Java实现 LeetCode 390 消除游戏
- 亲历H5移动端游戏微信支付接入及那些坑(四)——参考文档
- C/C++基础讲解(八十九)之游戏篇(迷宫探险游戏)
- Qt项目实战:方块游戏
- pyqt5实战之真爱游戏(2048改版)
- 聊聊游戏业务怎么用高斯Redis
- 强扩展、强一致、高可用…GaussDB成为游戏行业的心头爱
- 博弈问题--石头游戏(动态规划)
- 高仿精仿安卓疯狂猜图游戏源代码
- cocos2d-x 游戏优化方案
- 【Neo4j构建知识图谱】官方服务图谱大型数据集下载与可视化方法【数据集包括:食谱数据、足球、权力的游戏、美国宇航局、英国公司注册、财产所有权、政治捐款】
- 180行ruby代码搞定游戏2048
- 微信小程序(游戏)----拼图游戏(设计思路)
- 俄罗斯方块游戏培训相关文件