自动搬运

查看原文

来自洛谷，原作者为

	FendtSilence None

搬运于2025-08-24 21:40:01，当前版本为作者最后更新于2017-09-17 15:02:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题感觉无论是难度标签还是算法标签都有一些偏差。

这种最优化问题套路往往在DP之中，这里就来一种DP做法。

首先我们发现如果直接使用DP方程的话会有后效性，但是没有关系，我们先写出DP方程；

对于“n个物品选任意个”我们就可以想到一种递推方法，即设$f[i][j]$表示前$i$个物品选$j$个的最大收益

我们发现正着转移并不好转移，我们可以倒着转移，使选择的当前第$i$号物品为第一个物品，这样的话我们就发现这个物品对答案做的贡献就变成了$a[i].w-a[i].r*(j-1)$，于是写出转移方程：

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

以此得出，对于整个方程，我们要想使收益最大，在倒着转移的情况下贪心为$R_i$从大到小进行排序，而不是一开始的认为的从小到大排序。

献上代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int maxn=3001;
struct proj
{
    int w,r;
}a[maxn];
bool cmp(const proj &a,const proj &b)
{
    return a.r>b.r;
}
int f[maxn][maxn];
int n,ans;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].r;
    sort(a+1,a+1+n,cmp);
    f[1][1]=a[1].w;
    for(int i=1;i<=n;i++) for(int j=1;j<=i;j++)
    f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i].w-a[i].r*(j-1));
    for(int i=1;i<=n;i++) ans=max(f[n][i],ans);
    cout<<ans;
}
int main()
{
    solve();
    return 0;
}

这个题应该是动态规划的算法成分比较大，标签只有贪心是不是有失公正？