算法1
(DP) $O(40^4)$
我认为大部分同学可能刚开始跟我一样,状态设置为f[][][]分别代表到哪个点,选了几张牌以及当前这张牌选择哪个,或者是f[][]到哪个点,选了几张牌。
这样看上去似乎没毛病,但是,如果你先写了dfs,就会发现,这两个状态表示都无法解决哪张牌用了多少次,还剩多少次没有用。所以就需要换一种方法。
下面讲一下状态设置的思路;
首先,既然需要知道哪张牌用了多少次即能用多少次,就需要保存每个数字的数量,我首先设置的是f[][][][][][]分别表示到哪一步,总共用了几张牌,1用的次数,2用的次数.....,但是我发现空间不够,然后,我发现总共用了几张牌可以用1的次数与2的次数…累加,然后就优化了一位,但还是不够,然后又发现用1的次数乘1+2的次数乘2+3的次数乘3…可以表示到那个点,所以优化掉一维,由此,剩下了四维,可以保证空间足够。
这里说一下转移的思路;
状态设置完后,思路就比较清晰了,f[][][][][]要么上一次选的是1,要么选的是2....(有几种牌,就有几种转移)
f[i-1][j][k][u]表示上一次选的是1,依次类推,注意,需要先预处理出其是否有当前这种牌!!!
C++ 代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1e3;
int n,m;
int a[N],p[N];
int f[40][40][40][40];
int num[N];//每种卡牌个数
vector<int> s;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
cin>>p[i];
if(!num[p[i]]) s.push_back(p[i]);//记录牌的种类
num[p[i]]++;//记录每种牌的个数
}
f[0][0][0][0]=a[1];//注意加上起点的值!
if(s.size()==1)//只有一种牌
{
for(int i=0;i<=num[s[0]];i++)
if(i>=1) f[i][0][0][0]=max(f[i][0][0][0],f[i-1][0][0][0]+a[1+i*s[0]]);
cout<<f[num[s[0]]][0][0][0];
}else if(s.size()==2)//有2种牌
{
for(int i=0;i<=num[s[0]];i++)
for(int j=0;j<=num[s[1]];j++)
{
if(i>=1) f[i][j][0][0]=max(f[i][j][0][0],f[i-1][j][0][0]+a[1+i*s[0]+j*s[1]]);//上一次选第s[0]种牌
if(j>=1) f[i][j][0][0]=max(f[i][j][0][0],f[i][j-1][0][0]+a[1+i*s[0]+j*s[1]]);//上一次选第s[1]种牌
}
cout<<f[num[s[0]]][num[s[1]]][0][0];
}else if(s.size()==3)//有几种牌,就有几种转移
{
for(int i=0;i<=num[s[0]];i++)
for(int j=0;j<=num[s[1]];j++)
for(int k=0;k<=num[s[2]];k++)
{
if(i>=1) f[i][j][k][0]=max(f[i][j][k][0],f[i-1][j][k][0]+a[1+i*s[0]+j*s[1]+k*s[2]]);
if(j>=1) f[i][j][k][0]=max(f[i][j][k][0],f[i][j-1][k][0]+a[1+i*s[0]+j*s[1]+k*s[2]]);
if(k>=1) f[i][j][k][0]=max(f[i][j][k][0],f[i][j][k-1][0]+a[1+i*s[0]+j*s[1]+k*s[2]]);
}
cout<<f[num[s[0]]][num[s[1]]][num[s[2]]][0];
}else if(s.size()==4)
{
for(int i=0;i<=num[s[0]];i++)
for(int j=0;j<=num[s[1]];j++)
for(int k=0;k<=num[s[2]];k++)
for(int u=0;u<=num[s[3]];u++)
{
if(i>=1) f[i][j][k][u]=max(f[i][j][k][u],f[i-1][j][k][u]+a[1+i*s[0]+j*s[1]+k*s[2]+u*s[3]]);
if(j>=1) f[i][j][k][u]=max(f[i][j][k][u],f[i][j-1][k][u]+a[1+i*s[0]+j*s[1]+k*s[2]+u*s[3]]);
if(k>=1) f[i][j][k][u]=max(f[i][j][k][u],f[i][j][k-1][u]+a[1+i*s[0]+j*s[1]+k*s[2]+u*s[3]]);
if(u>=1) f[i][j][k][u]=max(f[i][j][k][u],f[i][j][k][u-1]+a[1+i*s[0]+j*s[1]+k*s[2]+u*s[3]]);
}
cout<<f[num[s[0]]][num[s[1]]][num[s[2]]][num[s[3]]];
}
return 0;
}
哭,我一开始也是全排列卡牌的顺序,但是发现复杂度太高,然后换成 ·
f[i][j]
的时候忘了卡牌顺序了思路分析不错