60pts，WA求调

原题链接：22616.乌龟棋

🥥

2026-02-05 21:12:23

发布于：上海

15阅读

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;
}

@Forwhy

有帮助，赞一个

去预览

0/2000

全部评论 1

Forwhy
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

全部评论 1

热门讨论