【题解】洛谷P1541[NOIP2010]乌龟棋 背包问题

题目链接

设 $dp[p1][p2][p3][p4]$dp[p1][p2][p3][p4] 表示分别选择 $p1,p2,p3,p4$p1,p2,p3,p4 张 $1,2,3,4$1,2,3,4 卡牌的最多分数。
$dp[p1][p2][p3][p4]=\max\{dp[p1-1][p2][p3][p4],dp[p1][p2-1][p3][p4],dp[p1][p2][p3-1][p4],dp[p1][p2][p3][p4-1]\}+a[1+p1+p2\times2+p3\times3+p4\times4]$dp[p1][p2][p3][p4]=max{dp[p1−1][p2][p3][p4],dp[p1][p2−1][p3][p4],dp[p1][p2][p3−1][p4],dp[p1][p2][p3][p4−1]}+a[1+p1+p2×2+p3×3+p4×4]

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[41][41][41][41],n,m,a[400],b[400],c[5];
int main()
{
	//freopen("in.txt","r",stdin);
    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",&b[i]),c[b[i]]++;
    dp[0][0][0][0]=a[1];
    for(int p1=0;p1<=c[1];p1++)
        for(int p2=0;p2<=c[2];p2++)
            for(int p3=0;p3<=c[3];p3++)
                for(int p4=0;p4<=c[4];p4++)
                {
                	int pos=1+p1+2*p2+3*p3+4*p4;//忘记+1了 
                	if(p1)dp[p1][p2][p3][p4]=max(dp[p1][p2][p3][p4],dp[p1-1][p2][p3][p4]+a[pos]);
                	if(p2)dp[p1][p2][p3][p4]=max(dp[p1][p2][p3][p4],dp[p1][p2-1][p3][p4]+a[pos]);
                	if(p3)dp[p1][p2][p3][p4]=max(dp[p1][p2][p3][p4],dp[p1][p2][p3-1][p4]+a[pos]);
                	if(p4)dp[p1][p2][p3][p4]=max(dp[p1][p2][p3][p4],dp[p1][p2][p3][p4-1]+a[pos]);
				}
	printf("%d\n",dp[c[1]][c[2]][c[3]][c[4]]);
	return 0;
}

总结

有意思