60pts,WA求调
2026-02-05 21:12:23
发布于:上海
17阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[351],b[5],dp[6][45][45][45];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
b[x]++;
}
dp[4][0][0][0]=a[1];
for(int i=2;i<=n;i++)
{
for(int j=0;j<=b[1];j++)
{
for(int k=0;k<=b[2];k++)
{
for(int x=0;x<=b[3];x++)
{
int z=i-1-j-2*k-3*x;
if(z%4==0 & z/4<=b[4])
{
dp[5][j][k][x]=0;
if(i>=2 && j>=1)dp[5][j][k][x]=max(dp[5][j][k][x],dp[4][j-1][k][x]+a[i]);
if(i>=3 && k>=1)dp[5][j][k][x]=max(dp[5][j][k][x],dp[3][j][k-1][x]+a[i]);
if(i>=4 && x>=1)dp[5][j][k][x]=max(dp[5][j][k][x],dp[2][j][k][x-1]+a[i]);
if(i>=5 && z>=1)dp[5][j][k][x]=max(dp[5][j][k][x],dp[1][j][k][x]+a[i]);
}
}
}
}
for(int i=1;i<=4;i++)
{
for(int j=0;j<=b[1];j++)
{
for(int k=0;k<=b[2];k++)
{
for(int x=0;x<=b[3];x++)
{
dp[i][j][k][x]=dp[i+1][j][k][x];
}
}
}
}
}
cout<<dp[5][b[1]][b[2]][b[3]];
return 0;
}
全部评论 1
1.先在外层循环遍历棋盘位置 i,然后内层遍历卡片数量。这样状态转移太复杂了。
而且因为同一个位置 i 可以由不同的卡片组合到达,还要准确记录每种卡片的剩余数量。2.if(z%4==0 & z/4<=b[4]) 这里应该是&&。
所以这道题不适用于枚举到位置,建议改成多维背包,用dp[i][j][k][l] 表示使用了 i 张1步卡、j 张2步卡、k 张3步卡、l 张4步卡后,能得到的最大分数。


2026-02-06 来自 日本
0







有帮助,赞一个