题解 P2647 【最大收益】

· · 题解

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

这种最优化问题套路往往在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;
}

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