【洛谷P2647】最大收益

题目大意

现在你面前有n个物品，编号分别为1，2，3，……，n。你可以在这当中任意选择任意多个物品。其中第i个物品有两个属性Wi和Ri，当你选择了第i个物品后，你就可以获得Wi的收益；但是，你选择该物品以后选择的所有物品的收益都会减少Ri。现在请你求出，该选择哪些物品，并且该以什么样的顺序选取这些物品，才能使得自己获得的收益最大。

注意，收益的减少是会叠加的。比如，你选择了第i个物品，那么你就会获得了Wi的收益；然后你又选择了第j个物品，你又获得了Wj-Ri收益；之后你又选择了第k个物品，你又获得了Wk-Ri-Rj的收益；那么你获得的收益总和为Wi+(Wj-Ri)+(Wk-Ri-Rj)。

题解

同 洛谷P1417。

只不过在计算答案贡献时，发现正序枚举的时间复杂度是 \(O(N^3)\)，即：决策的时间复杂度达到了 \(O(N)\)。在这里可以采用对物品进行逆向排序，这样每次选择的时候，将当前决策的物品作为第一个选择的物品，可以发现，这对后面物品对答案的贡献减少了 \(val*(j-1)\)，即可在 \(O(1)\) 决策。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=3010;

int n,dp[maxn][maxn];

struct node{int r,w;}a[maxn];

bool cmp(const node &x,const node &y){

	return x.r>y.r;

}

void read_and_parse(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].r);

	sort(a+1,a+n+1,cmp);

}

void solve(){

	for(int i=1;i<=n;i++)

		for(int j=1;j<=i;j++)

			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i].w-(j-1)*a[i].r);

	int ans=0;

	for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);

	printf("%d\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}