比赛 |
防止颓废的小练习v0.2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
乌龟棋 |
最终得分 |
100 |
用户昵称 |
农场主 |
运行时间 |
0.330 s |
代码语言 |
C++ |
内存使用 |
92.57 MiB |
提交时间 |
2016-10-18 19:33:47 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 41
using namespace std;
int d[351][maxn][maxn][maxn]={0};
int v[351]={0};
int c[5]={0},n,m,ans=0;
int num(int s,int a2,int a3,int a4){
return s-a2*2-a3*3-a4*4;
}
void read(){
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++){
scanf("%d",&v[i]);
}
for (int i=1;i<=m;i++){
int p;
scanf("%d",&p);
c[p]++;
}
}
bool check(int x,int a2,int a3,int a4){
int a1=num(x,a2,a3,a4);
if (a1<0) return 0;
if (a1>c[1]||a2>c[2]||a3>c[3]||a4>c[4]) return 0;
return 1;
}
void update(int x,int a2,int a3,int a4){
int& now=d[x][a2][a3][a4];
if (x-1>=0) now=max(now,d[x-1][a2][a3][a4]+v[x]);
if (x-2>=0&&a2>0) now=max(now,d[x-2][a2-1][a3][a4]+v[x]);
if (x-3>=0&&a3>0) now=max(now,d[x-3][a2][a3-1][a4]+v[x]);
if (x-4>=0&&a4>0) now=max(now,d[x-4][a2][a3][a4-1]+v[x]);
ans=max(ans,now);
}
int main(){
freopen("tortoise.in","r",stdin);
freopen("tortoise.out","w",stdout);
read();
// printf("%d %d %d %d\n",c[1],c[2],c[3],c[4]);
d[0][0][0][0]=v[0];
for (int i=1;i<n;i++){
for (int j=0;j<=c[2];j++){
if (j*2>i) break;
for (int k=0;k<=c[3];k++){
if (j*2+k*3>i) break;
for (int l=0;l<=c[4];l++){
if (j*2+k*3+l*4>i) break;
// printf("%d\n",check(i,j,k,l));
if (check(i,j,k,l)){
update(i,j,k,l);
// printf("%d %d %d %d %d\n",i,num(i,j,k,l),j,k,l);
}
}
}
}
}
printf("%d",ans);
return 0;
}