#include<iostream>
using namespace std;
int m,n,s[10000],t[10],f[41][41][41][41],i,j,k,l;
main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>s[i];
for(i=1;i<=m;i++)
{
cin>>j;
t[j]++;
}
for(i=1;i<=t[1]+1;i++)
for(j=1;j<=t[2]+1;j++)
for(k=1;k<=t[3]+1;k++)
for(l=1;l<=t[4]+1;l++)
f[i][j][k][l]=max(max(f[i-1][j][k][l],f[i][j-1][k][l]),max(f[i][j][k-1][l],f[i][j][k][l-1]))+s[i+j*2+k*3+l*4-9];
cout<<f[t[1]+1][t[2]+1][t[3]+1][t[4]+1];
}

#include <cstdio>
#include <iostream>
using namespace std;
int f[41][41][41][41];
int p[5],v[351];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++)
scanf("%d",v+i);
for (int i=1,x;i<=m;i++)
scanf("%d",&x),p[x]++;
f[0][0][0][0]=v[0];
for (int i=0;i<=p[1];i++)
for (int j=0;j<=p[2];j++)
for (int k=0;k<=p[3];k++)
for (int l=0;l<=p[4];l++)
{
int u=i+j*2+k*3+l*4;
if (i) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+v[u]);
if (j) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+v[u]);
if (k) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+v[u]);
if (l) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+v[u]);
}
printf("%d\n",f[p[1]][p[2]][p[3]][p[4]]);
return 0;
}

秒杀

#include<cstdio>
#define IOFileName "tortoise"
const int maxn=351,maxx=45;
int n,m;
int a[maxn]={0},b[5]={0};
int map[maxx][maxx][maxx][maxx]={0};
int main(){
//freopen(IOFileName".in","r",stdin);
//freopen(IOFileName".out","w",stdout);
scanf("%d %d\n",&n,&m);
for(int i=0;i<n;i++){scanf("%d ",&a[i]);}scanf("\n");
map[0][0][0][0]=a[0];
for(int i=0,x;i<m;i++){scanf("%d ",&x);b[x]++;}
for(int A=0;A<=b[1];A++){
for(int B=0;B<=b[2];B++){
for(int C=0;C<=b[3];C++){
for(int D=0;D<=b[4];D++){
if(A>0&&map[A][B][C][D]<map[A-1][B][C][D]+a[A*1+B*2+C*3+D*4]){
map[A][B][C][D]=map[A-1][B][C][D]+a[A*1+B*2+C*3+D*4];
}
if(B>0&&map[A][B][C][D]<map[A][B-1][C][D]+a[A*1+B*2+C*3+D*4]){
map[A][B][C][D]=map[A][B-1][C][D]+a[A*1+B*2+C*3+D*4];
}
if(C>0&&map[A][B][C][D]<map[A][B][C-1][D]+a[A*1+B*2+C*3+D*4]){
map[A][B][C][D]=map[A][B][C-1][D]+a[A*1+B*2+C*3+D*4];
}
if(D>0&&map[A][B][C][D]<map[A][B][C][D-1]+a[A*1+B*2+C*3+D*4]){
map[A][B][C][D]=map[A][B][C][D-1]+a[A*1+B*2+C*3+D*4];
}
}
}
}
}
printf("%d\n",map[b[1]][b[2]][b[3]][b[4]]);
}
91MS+16296KB

/*
* =====================================================================================
*
* Filename: d893.cpp
*
* Description:

*
* Version: 1.0
* Created: Thursday, 06/26/2014 11:47:54 PM
* Revision: none
* Compiler: gcc
*
* Author: Terry Cheong. (terry182)
* Organization:

*
* =====================================================================================
*/

#include <cstdio>
#include <cstring>
const int maxn = 350+5;
int n, m;
int a[maxn], card[5];
int dp[45][45][45][45];

inline int max(int a, int b)
{ return (a > b)?a : b;
}

int main()
{ scanf("%d%d", &n, &m);
memset(card, 0, sizeof(card));
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++)
{ int tmp;
scanf("%d", &tmp);
card[tmp]++;
}
dp[0][0][0][0] = a[0];
for (int i = 0; i <= card[1]; i++)
for (int j = 0; j <= card[2]; j++)
for (int k = 0; k <= card[3]; k++)
for (int l = 0; l <= card[4]; l++)
{ int p = i+2*j+3*k+4*l;
if (i > 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l]+a[p]);
if (j > 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l]+a[p]);
if (k > 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k-1][l]+a[p]);
if (l > 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l-1]+a[p]);
}
printf("%d\n", dp[card[1]][card[2]][card[3]][card[4]]);
return 0;
}
四維DP

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

四维DP水过~
编译成功

测试数据 #0: Accepted, time = 78 ms, mem = 97636 KiB, score = 10
测试数据 #1: Accepted, time = 62 ms, mem = 97632 KiB, score = 10
测试数据 #2: Accepted, time = 78 ms, mem = 97636 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 97632 KiB, score = 10
测试数据 #4: Accepted, time = 78 ms, mem = 97640 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 97636 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 97640 KiB, score = 10
测试数据 #7: Accepted, time = 140 ms, mem = 97636 KiB, score = 10
测试数据 #8: Accepted, time = 125 ms, mem = 97632 KiB, score = 10
测试数据 #9: Accepted, time = 125 ms, mem = 97636 KiB, score = 10
Accepted, time = 981 ms, mem = 97640 KiB, score = 100
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 360
#define MAXB 41

int f[MAXN][MAXB][MAXB][MAXB];
int v[MAXN];
int m,n;
int a1,a2,a3,a4;

int main(){
scanf("%d%d",&n,&m);
a1=a2=a3=a4=0;
for (int i=0;i++<n;){
scanf("%d",&v[i]);
}
while (m--){
int x;
scanf("%d",&x);
switch (x){
case 1:
a1++;
break;
case 2:
a2++;
break;
case 3:
a3++;
break;
case 4:
a4++;
break;
}
}
memset(f,0,sizeof(f));
f[1][0][0][0]=v[1];
for (int i=1;i++<n;){
for (int j=0;j<=a2;j++){
for (int k=0;k<=a3;k++){
for (int h=0;h<=a4;h++){
if (i-1>0){
if (f[i-1][j][k][h]){
f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k][h]+v[i]);
}
}
if (i-2>0&&j){
if (f[i-2][j-1][k][h]){
f[i][j][k][h]=max(f[i][j][k][h],f[i-2][j-1][k][h]+v[i]);
}
}
if (i-3>0&&k){
if (f[i-3][j][k-1][h]){
f[i][j][k][h]=max(f[i][j][k][h],f[i-3][j][k-1][h]+v[i]);
}
}
if (i-4>0&&h){
if (f[i-4][j][k][h-1]){
f[i][j][k][h]=max(f[i][j][k][h],f[i-4][j][k][h-1]+v[i]);
}
}
}
}
}
}
printf("%d\n",f[n][a2][a3][a4]);
return 0;
}

四维DP，不怎好调试。。
输出的东西写错了，调试了半天都没调试出来。
这条题目是以卡片来DP的

转移方程： card[x,y,z,w]=max{card[x-1,y,z,w],card[x,y-1,z,w],card[x,y,z-1,w],card[x,y,z,w-1]}+map[x+2*y+3*z+4*w]

附上没秒杀的程序
program p1775;
var card:array[-1..41,-1..41,-1..41,-1..41] of longint;
c1,c2,c3,c4,n,m,i,j,k,l,x,y,z,w:longint;
map:array[0..351] of longint;
cc:array[1..4] of integer;
function max(a,b,c,d:longint):longint;
begin
max:=a;
if b>max then max:=b;
if c>max then max:=c;
if d>max then max:=d;
end;

begin
readln(n,m);
for i:=1 to n do read(map[i]);
for i:=1 to m do begin read(k);inc(cc[k]);end;
for x:=0 to cc[1] do
for y:=0 to cc[2] do
for z:=0 to cc[3] do
for w:=0 to cc[4] do
card[x,y,z,w]:=max(card[x-1,y,z,w],card[x,y-1,z,w],card[x,y,z-1,w],card[x,y,z,w-1])+map[x+y+y+z+z+z+w+w+w+w+1];
writeln(card[x,y,z,w]);
end.

//c++ version
#include<cstdio>
#include<cstring>
#define max(a,b) a>b?a:b
int dp[49][49][49][49],score[351],m=0,n=0,k[5]={0};
int find(int a,int b,int c,int d)
{
if(dp[a][b][c][d]!=-1)
{
return dp[a][b][c][d];
}
int pos=a+b*2+c*3+d*4;
dp[a][b][c][d]=score[pos];
if(a>0)
dp[a][b][c][d]=max(dp[a][b][c][d],score[pos]+find(a-1,b,c,d));
if(b>0)
dp[a][b][c][d]=max(dp[a][b][c][d],score[pos]+find(a,b-1,c,d));
if(c>0)
dp[a][b][c][d]=max(dp[a][b][c][d],score[pos]+find(a,b,c-1,d));
if(d>0)
dp[a][b][c][d]=max(dp[a][b][c][d],score[pos]+find(a,b,c,d-1));
return dp[a][b][c][d];
}
int main()
{
int temp=0;
while(scanf("%d%d",&n,&m)==2)
{
memset(dp,-1,sizeof(dp));
memset(k,0,sizeof(k));
for(int i=0;i<n;i++)
scanf("%d",&score[i]);
for(int i=0;i<m;i++)
{
scanf("%d",&temp);
k[temp]++;
}
dp[0][0][0][0]=score[0];
dp[k[1]] [k[2]] [k[3]] [k[4]]=find(k[1],k[2],k[3],k[4]);
printf("%d\n",dp[k[1]][k[2]][k[3]][k[4]]);
}
return 0;
}

var
n,m,i,k,i1,i2,i3,i4:longint;
a,s:array[0..355] of longint;
f:array[-1..41,-1..41,-1..41,-1..41] of longint;
function max(a,b,c,d,e:longint):longint;
begin
max:=a;
if b>max then max:=b;
if c>max then max:=c;
if d>max then max:=d;
if e>max then max:=e;
end;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
for i:=1 to m do
begin
read(k);
inc(s[k]);
end;
for i1:=0 to s[1] do
for i2:=0 to s[2] do
for i3:=0 to s[3] do
for i4:=0 to s[4] do
f[i1,i2,i3,i4]:=max(f[i1,i2,i3,i4],
f[i1-1,i2,i3,i4],
f[i1,i2-1,i3,i4],
f[i1,i2,i3-1,i4],
f[i1,i2,i3,i4-1])+a[i1+2*i2+3*i3+4*i4+1];
writeln(f[s[1],s[2],s[3],s[4]]);
end.

DP吗？

四维DP

#include<iostream>
using namespace std;
int map[360],dp[41][41][41][41],a[5];
int main()
{
    int n,i,j,k,u,m,ha;
    cin>>n>>m;
    for(i=0;i<n;i++)
     cin>>map[i];
    for(i=1;i<=m;i++)
    {
        cin>>ha;
        a[ha]++;
    }
    dp[0][0][0][0]=map[0];
    for(i=0;i<=a[1];i++)
     for(j=0;j<=a[2];j++)
      for(k=0;k<=a[3];k++)
       for(u=0;u<=a[4];u++)
       {
        dp[i+1][j][k][u]=max(dp[i+1][j][k][u],dp[i][j][k][u]+map[i+1+2*j+3*k+4*u]);
        dp[i][j+1][k][u]=max(dp[i][j+1][k][u],dp[i][j][k][u]+map[i+2+2*j+3*k+4*u]);
        dp[i][j][k+1][u]=max(dp[i][j][k+1][u],dp[i][j][k][u]+map[i+3+2*j+3*k+4*u]);
        dp[i][j][k][u+1]=max(dp[i][j][k][u+1],dp[i][j][k][u]+map[i+4+2*j+3*k+4*u]);
        }
    cout<<dp[a[1]][a[2]][a[3]][a[4]];
    return 0;
}

水题，一眼看出

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int a[351]={0},book[5]={0},f[40][40][40][40]={0};
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int b;
        scanf("%d",&b);
        book[b]++;
    }
    f[0][0][0][0]=a[1];
    for(int i1=0;i1<=book[1];i1++)
    {
        for(int i2=0;i2<=book[2];i2++)
        {
            for(int i3=0;i3<=book[3];i3++)
            {
                for(int i4=0;i4<=book[4];i4++)
                {
                    int bla=a[1+i1+i2*2+i3*3+i4*4];
                    if(i1>=1)
                        f[i1][i2][i3][i4]=f[i1-1][i2][i3][i4]+bla;
                    if(i2>=1)
                        f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2-1][i3][i4]+bla);
                    if(i3>=1)
                        f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2][i3-1][i4]+bla);
                    if(i4>=1)
                        f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2][i3][i4-1]+bla);
                }
            }   
        }
    }
    printf("%d",f[book[1]][book[2]][book[3]][book[4]]);
    return 0; 
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int a[350+1];
int b[120+1];
int c[4+1];
int f[40+1][40+1][40+1][40+1];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(c,0,sizeof(c));
        for (int i=1;i<=m;i++)
        {
            scanf("%d",&b[i]);
            c[b[i]]++;
        }
        memset(f,0,sizeof(f));
        f[0][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 l=0;l<=c[4];l++)
                    {
                        int now=i+(2*j)+(3*k)+(4*l)+1;
                        if (i>=1)
                            f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[now]);
                        if (j>=1)
                            f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[now]);
                        if (k>=1)
                            f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[now]);
                        if (l>=1)
                            f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[now]);
                    }
        printf("%d\n",f[c[1]][c[2]][c[3]][c[4]]);
    }
}

//
var
  a:array[1..350] of longint;
  b:array[1..4] of longint;
  f:array[-1..40, -1..40, -1..40, -1..40] of longint;
  n, m, i, j, k, r, x:longint;
function max(c, d, e, g:longint):longint;
begin
  if c>d then max:=c
  else max:=d;
  if e>max then max:=e;
  if g>max then max:=g
end;
begin
  readln(n, m);
  for i:=1 to n do read(a[i]);
  fillchar(b, sizeof(b), 0);
  for i:=1 to m do begin
    read(x);
    inc(b[x])
  end;
  fillchar(f, sizeof(f), 0);
  for i:=0 to b[1] do
    for j:=0 to b[2] do
      for k:=0 to b[3] do
        for r:=0 to b[4] do begin
          x:=i+j*2+k*3+r*4+1;
          if max(f[i-1, j, k, r], f[i, j-1, k, r], f[i, j, k-1, r], f[i, j, k, r-1])+a[x]>f[i, j, k, r] then f[i, j, k, r]:=max(f[i-1, j, k, r], f[i, j-1, k, r], f[i, j, k-1, r], f[i, j, k, r-1])+a[x]
        end;
  write(f[b[1], b[2], b[3], b[4]])
end.

测试数据 #0: Accepted, time = 0 ms, mem = 11804 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 11800 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 11804 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 11800 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 11804 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 11804 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 11800 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 11804 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 11804 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 11804 KiB, score = 10
Accepted, time = 30 ms, mem = 11804 KiB, score = 100

#include <cstdio>
#include <algorithm>
using std::max;

int t,n,m,a[400],card[5]={0},f[50][50][50][50]={0};

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d",&t);
card[t]++;
}
for(int p1=0;p1<=card[1];p1++)
for(int p2=0;p2<=card[2];p2++)
for(int p3=0;p3<=card[3];p3++)
for(int p4=0;p4<=card[4];p4++){
t=0;
if(p1) t=max(t,f[p1-1][p2][p3][p4]);
if(p2) t=max(t,f[p1][p2-1][p3][p4]);
if(p3) t=max(t,f[p1][p2][p3-1][p4]);
if(p4) t=max(t,f[p1][p2][p3][p4-1]);

f[p1][p2][p3][p4]=t+a[1+p1*1+p2*2+p3*3+p4*4];
}

printf("%d",f[card[1]][card[2]][card[3]][card[4]]);
return 0;
}

代码还算简洁易懂，想学记忆化搜索的同学可以看下：
顺便安利一下个人博客：haogram.hol.es
```
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[45][45][45][45];
bool vis[45][45][45][45];
int n, m, t;
static int w[400], num[5];

void Input() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d", &w[i]);
memset(num, 0, sizeof(num));
while(m--) {
scanf("%d", &t);
num[t]++;
}
}

int DFS(int n, int a, int b, int c, int d) {
if( n<1 || a<0 || b<0 || c<0 || d<0 ) return 0;
if(vis[a][b][c][d]) return dp[a][b][c][d];
dp[a][b][c][d] = max(dp[a][b][c][d], DFS(n-1, a-1, b, c, d));
dp[a][b][c][d] = max(dp[a][b][c][d], DFS(n-2, a, b-1, c, d));
dp[a][b][c][d] = max(dp[a][b][c][d], DFS(n-3, a, b, c-1, d));
dp[a][b][c][d] = max(dp[a][b][c][d], DFS(n-4, a, b, c, d-1));
dp[a][b][c][d] += w[n];
vis[a][b][c][d] = true;
return dp[a][b][c][d];
}

void Solve() {
memset(dp, 0, sizeof(dp));
memset(vis, false, sizeof(vis));
vis[0][0][0][0] = true;
dp[0][0][0][0] = w[1];
DFS(n, num[1], num[2], num[3], num[4]);
printf("%d", dp[num[1]][num[2]][num[3]][num[4]]);
}

int main() {
Input();
Solve();
return 0;
}
```