讨论 / 水题一个
fnoichzhe 2018-07-08 22:30:48
点我顶贴 收藏 删除
#include<cstdio>

#include<cstring>

//定义队列中的节点

int n,m,b[5],c[385],x,op,cl,a1,a2,a3,a4;

struct node{

int a1,a2,a3,a4;

};

//定义队列q

node q[3000000];

//定义数组判重

bool flag[44][44][44][44];

int f[44][44][44][44];

int main(){

//freopen("caioj1542.in","r",stdin);

scanf("%d%d",&n,&m);

b[1]=b[2]=b[3]=b[4]=0;

for(int i=1;i<=n;++i){

scanf("%d",&c[i]);

}

for(int i=1;i<=m;++i){

scanf("%d",&x);

b[x]++;

}

//初始化

memset(f,0,sizeof f);

memset(flag,true,sizeof flag);

f[0][0][0][0]=c[1];

q[1].a1=q[1].a2=q[1].a3=q[1].a4=0;

flag[0][0][0][0]=false;

op=0;

cl=1;

while(op<cl){

++op;

//取出op位置的状态

a1=q[op].a1;

a2=q[op].a2;

a3=q[op].a3;

a4=q[op].a4;

//对a1操作

if(a1+1<=b[1]){

int maxa=f[a1][a2][a3][a4]+c[a1+1+2*a2+3*a3+4*a4+1];

if(f[a1+1][a2][a3][a4]<maxa)f[a1+1][a2][a3][a4]=maxa;

//a1+1,a2,a3,a4准备入队

if(flag[a1+1][a2][a3][a4]){

++cl;

q[cl].a1=a1+1;

q[cl].a2=a2;

q[cl].a3=a3;

q[cl].a4=a4;

flag[a1+1][a2][a3][a4]=false;

}

}

//对a2操作

if(a2+1<=b[2]){

int maxa=f[a1][a2][a3][a4]+c[a1+2*(a2+1)+3*a3+4*a4+1];

if(f[a1][a2+1][a3][a4]<maxa)f[a1][a2+1][a3][a4]=maxa;

//a1+1,a2,a3,a4准备入队

if(flag[a1][a2+1][a3][a4]){

++cl;

q[cl].a1=a1;

q[cl].a2=a2+1;

q[cl].a3=a3;

q[cl].a4=a4;

flag[a1][a2+1][a3][a4]=false;

}

}

//对a3操作

if(a3+1<=b[3]){

int maxa=f[a1][a2][a3][a4]+c[a1+2*a2+3*(a3+1)+4*a4+1];

if(f[a1][a2][a3+1][a4]<maxa)f[a1][a2][a3+1][a4]=maxa;

//a1+1,a2,a3,a4准备入队

if(flag[a1][a2][a3+1][a4]){

++cl;

q[cl].a1=a1;

q[cl].a2=a2;

q[cl].a3=a3+1;

q[cl].a4=a4;

flag[a1][a2][a3+1][a4]=false;

}

}

//对a4操作

if(a4+1<=b[4]){

int maxa=f[a1][a2][a3][a4]+c[a1+2*a2+3*a3+4*(a4+1)+1];

if(f[a1][a2][a3][a4+1]<maxa)f[a1][a2][a3][a4+1]=maxa;

//a1+1,a2,a3,a4准备入队

if(flag[a1][a2][a3][a4+1]){

++cl;

q[cl].a1=a1;

q[cl].a2=a2;

q[cl].a3=a3;

q[cl].a4=a4+1;

flag[a1][a2][a3][a4+1]=false;

}

}

}

printf("%d",f[b[1]][b[2]][b[3]][b[4]]);

return 0;

}

查看更多回复
提交回复