一道无脑的线性DP
貌似可以压成三维?
因为这是最优性DP
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=355,M=42;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int f[M][M][M],c[5],a[N];
int main()
{
int cnt=0,n,m;qr(n),qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
for(int i=1,x;i<=m;i++)qr(x),++c[x];
cnt=c[1]+c[2]+c[3]+c[4];
memset(f,0xcf,sizeof(f));f[0][0][0]=a[1];
for(int i=0;i<=c[1];i++)//滚掉一维
for(int j=0;j<=c[2];j++)
for(int k=0;k<=c[3];k++)
for(int w=0;w<=c[4];w++)
{
int now=i+j*2+k*3+w*4+1;
if(i>0)f[j][k][w]=f[j][k][w]+a[now];//f[i][j][k][w]=f[i-1][j][k][w]+a[now];
if(j>0)f[j][k][w]=max(f[j][k][w],f[j-1][k][w]+a[now]);
if(k>0)f[j][k][w]=max(f[j][k][w],f[j][k-1][w]+a[now]);
if(w>0)f[j][k][w]=max(f[j][k][w],f[j][k][w-1]+a[now]);
}
qw(f[c[2]][c[3]][c[4]]);puts("");
return 0;
}
最后一次更新于2019-10-25
0 条评论