sb题目存档
White_gugu · · 个人记录
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[10][5]={
{127,65,65,127,0},
{0,0,0,127,0},
{121,73,73,79,0},
{73,73,73,127,0},
{15,8,8,127,0},
{79,73,73,121,0},
{127,73,73,121,0},
{1,1,1,127,0},
{127,73,73,127,0},
{79,73,73,127,0}
};
int n,ch,pw[10],cnt[220];
int eA[2020],a[2020],to[2020][2020],hzh[2020];
int ans_a[2020],ans_b[2020],ans_c[2020],ans;
int dp_1[2020][11],dp_2[2020][11],dp_3[2020][11],dp_4[2020][11],g[2020][2020];
bool bz[2020][2020];
int get_sum(int x,int y){
int sum=0;
for(int i=0;i<=4;i++)
sum=sum+cnt[(a[x+i]^num[y][i])];
return sum;
}
void init(){
memset(eA,0,sizeof(eA));
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=1;i<=7;i++)
for(int j=1;j<=n;j++){
ch=getchar();
while(ch!='X'&&ch!='.') ch=getchar();
if(ch=='X') eA[j]++,a[j]+=pw[i-1];
}
for(int i=1;i<=n;i++)
for(int j=0;j<10;j++)
to[i][j]=get_sum(i,j);
}
void dis_1(int *mmp){
init();
memset(dp_1,127/3,sizeof(dp_1));
memset(dp_2,127/3,sizeof(dp_2));
memset(dp_3,127/3,sizeof(dp_3));
memset(dp_4,127/3,sizeof(dp_4));
memset(hzh,127/3,sizeof(hzh));
hzh[n+2]=hzh[n+1]=0;
int s=0;
for(int i=0;i<=n;i++){
s+=eA[i];
// printf("%d %d\n",s,eA[i+1]);
for(int j=0;j<=2;j++){
dp_1[i+5][j]=min(dp_1[i+5][j],s+to[i+1][j]);
dp_1[i+1][j]=min(dp_1[i+1][j],dp_1[i][j]+eA[i+1]);
}
for(int j=0;j<=9;j++){
dp_2[i+1][j]=min(dp_2[i+1][j],dp_2[i][j]+eA[i+1]);
dp_2[i+1][j+10]=min(dp_2[i+1][j+10],dp_2[i][j+10]+eA[i+1]);
dp_2[i+5][j]=min(dp_2[i+5][j],dp_1[i][0]+to[i+1][j]);
dp_2[i+5][j+10]=min(dp_2[i+5][j+10],dp_1[i][1]+to[i+1][j]);
}
// for(int j=0;j<10;++j){
// upd(L[i+1][j],L[i][j]+t);
// upd(L[i+1][10+j],L[i][10+j]+t);
// upd(L[i+5][j],l[i][0]+a[i+1][j]);
// upd(L[i+5][10+j],l[i][1]+a[i+1][j]);
// }
for(int j=0;j<=3;j++){
dp_2[i+1][j+20]=min(dp_2[i+1][j+20],dp_2[i][j+20]+eA[i+1]);
dp_2[i+5][j+20]=min(dp_2[i+5][j+20],dp_1[i][2]+to[i+1][j]);
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<=23;j++)
printf("%d %d %d\n",i,j,dp_2[i][j]);
for(int i=n;i>=0;i--){
hzh[i]=hzh[i+1]+eA[i];
for(int j=0;j<=9;j++){
dp_4[i][j]=min(dp_4[i][j],hzh[i+5]+to[i][j]);
dp_4[i][j]=min(dp_4[i][j],dp_4[i+1][j]+eA[i]);
}
for(int j=0;j<=5;j++)
for(int k=0;k<=9;k++){
dp_3[i][j*10+k]=min(dp_3[i][j*10+k],dp_3[i+1][j*10+k]+eA[i]);
dp_3[i][j*10+k]=min(dp_3[i][j*10+k],dp_4[i+5][k]+to[i][j]);
}
}
for(int i=0;i<=23;i++)
for(int j=0;j<=59;j++)
for(int k=1;k<=n;k++){
mmp[i*60+j]=min(mmp[i*60+j],dp_2[k-1][i]+dp_3[k+2][j]+eA[k+1]+cnt[(a[k])^(pw[2]+pw[4])]);
// if(i*60+j==60){
// printf("%d %d %d %d\n",mmp[60],k,dp_2[k-1][i],dp_3[k+2][j]);
// }
}
}
void dis_2(int *mmp){
init();
memset(g,127/3,sizeof(g));
g[0][0]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=1439;j++){
if(g[i+1][j]>g[i][j]+eA[i+1])
g[i+1][j]=g[i][j]+eA[i+1],bz[i+1][j]=bz[i][j];
for(int k=0;k<=9;k++){
if(g[i+5][(j*10+k)%1440]>g[i][j]+to[i+1][k]){
if(k==0&&bz[i][j]==0) continue;
g[i+5][(j*10+k)%1440]=g[i][j]+to[i+1][k];
bz[i+5][(j*10+k)%1440]=1;
}
}
}
int s=0,now=0;
for(int i=1;i<=n;i++)
s+=eA[i];
now=now+eA[1]+eA[2]+eA[3]+eA[4]+eA[5];
for(int i=1;i<=n-4;i++){
mmp[0]=min(mmp[0],s-now+to[i][0]);
now=now-eA[i]+eA[i+5];
}
for(int i=0;i<=1439;i++){
if(bz[n][i]) mmp[i]=min(mmp[i],g[n][i]);
if(bz[n+1][i]) mmp[i]=min(mmp[i],g[n+1][i]);
}
return;
}
int main(){
ans=2147483647;
memset(ans_a,127/3,sizeof(ans_a));
memset(ans_b,127/3,sizeof(ans_b));
memset(ans_c,127/3,sizeof(ans_c));
pw[0]=1;
for(int i=1;i<=7;i++) pw[i]=pw[i-1]*2;
for(int i=1;i<=(1<<7);i++) cnt[i]=cnt[i>>1]+(i&1);
dis_1(ans_a);
// for(int i=0;i<=100;i++)
// printf("%d %d\n",i,ans_a[i]);
dis_2(ans_b);
dis_1(ans_c);
// for(int i=0;i<=200;i++)
// printf("%d %d\n",i,ans_b[i]);
for(int i=0;i<=1439;i++)
for(int j=0;j<=1439;j++)
ans=min(ans,ans_a[i]+ans_b[j]+ans_c[(i+j)%1440]);
printf("%d\n",ans);
}