单向前进,每个点有权值,要求路径权值和最大。这不是显然的DP。但是这题对前进的步伐有四种,每种还有次数限制。。这就不好搞。朴素点的就是开四维DP。然后枚举,从前往后枚举。再看一下数据,还真的是。。
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T max(T &a, T &b) {
return a > b ? a : b;
}
template<typename T>
inline T min(T &a, T &b) {
return a < b ? a : b;
}
inline char gt() {
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void read(T &x) {
register char ch = gt();
x = 0;
int w(0);
while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
if(x < 0) x = -x, putchar('-');
char ch[20];
int num(0);
while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
while(num) putchar(ch[num--]);
putchar('\n');
}
const int N = 407;
const int M = 127;
int n, m, a[N], num[N];
int f[47][47][47][47];
int main() {
read(n);
read(m);
rep(i, 1, n) {
read(a[i]);
}
rep(i, 1, m) {
int x;
read(x);
num[x]++;
}
f[0][0][0][0]=a[1];
rep(i,0,num[1])
rep(j,0,num[2])
rep(k,0,num[3])
rep(h,0,num[4]){
int pos=1+i+2*j+3*k+4*h;
if(i) f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k][h]+a[pos]);
if(j) f[i][j][k][h]=max(f[i][j][k][h],f[i][j-1][k][h]+a[pos]);
if(k) f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k-1][h]+a[pos]);
if(h) f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k][h-1]+a[pos]);
}
out(f[num[1]][num[2]][num[3]][num[4]]);
return 0;
}