P4912帕秋莉的魔法（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 5.1k | 阅读时长 ≈ 5 分钟

这里有一篇题解。

P4912帕秋莉的魔法（题解）

点我

PS.

楼上的题解解释较少，希望这篇题解能帮助到你

Problem.

有$\texttt{n}$个物品，每个物品有一个重量和一个价值，只能从前往后取物品。
取了前面的物品之后会对下一个物品有一定的影响，使后一个物品的价值加上一个值。
现在，你需要取重量和恰好为$\texttt{n}$的一些物品，使它们的价值和最大。

Solution.

首先，每一个物品有两个属性，第一时间想到的应该是背包。
所以根据背包常用套路，设$\texttt{dp[x][y]}$表示前$\texttt{x}$个物品中取出重量恰为$\texttt{y}$的最大价值和。
所以$\texttt{dp[x][y+a[x]]=max(dp[k][y]+b[x]+w[k][x])}$。

Attention.

这道题如果这样写的话不会得到全分，具体得分未亲测。
因为这题中$\texttt{w}$可能为负数，如果单纯这样写会$\texttt{RE}$或$\texttt{WA}$。
所以我们可以给第二位加一个偏移量，相当于程序中的$\texttt{dp[i][j]}$表示我们的$\texttt{dp[i][j-2500]}$。
这样就能得全分了QwQ

Coding.

压行码风勿喷QwQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
const int N=55,V=2500;	//V：注意点重的偏移量
int n,m,ans,a[N],b[N],w[N][N],dp[N][(V<<1)+5];	//此处解释略
int main()
{
	scanf("%d%d",&n,&m);	//读入
	for(int i=1;i<=n;i++) scanf("%d%d",a+i,b+i);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&w[i][j]);
	memset(dp,~0x3f,sizeof(dp)),dp[0][V]=0;		//初始化为最小值，方便以后处理
	for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=(V<<1);k>=0;k--) if(dp[i][k]!=dp[0][0]) dp[j][k+a[j]]=max(dp[j][k+a[j]],dp[i][k]+b[j]+w[i][j]);	//最关键的一行语句，动态规划转移
	ans=dp[0][0];for(int i=1;i<=n;i++) ans=max(ans,dp[i][m+V]);		//从所有恰好为m条语句中找出答案
	return (ans==dp[0][0]?puts("-1"):printf("%d\n",ans)),0;	//完美地一行输出
}

拒绝抄袭代码，营造良好洛谷