luogu P12678

题
只是一道绿啊。。

转化题意

把每一个人的贡献都提出来一个 \(a\)，这样第一种情况贡献为 \(0\)，第二种贡献为 \(a_i(b_i-1)\)。

思路

对于一种排列，显然他们其中有贡献的人的 \(b\) 按升序排序。

而我们可以把这些人全部移到队伍前面，这样有贡献的人肯定还是有贡献，这是不会使答案减少的。

所以我们只用考虑（有贡献的人只在队伍前缀）的情况。

而不在这个前缀里的人就看作被扔掉了。

这又相当于什么？

在一个按 \(b\) 升序排列的序列里，选出一个可行的子序列的人来做贡献。

然后就可以 DP 了。

定义 \(d_j\) 表示到了当前点（设为 \(i\)），所选 \(b\) 的总和为 \(j\) 所能造成的最大贡献。

转移很好写了。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+5;
long long n,d[maxn],ans,s;
struct xxx
{
    long long x,y;
    bool operator < (const xxx o) const {return y<o.y;}
    bool operator > (const xxx o) const {return y>o.y;}
}a[maxn];
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x;
    for(int i=1;i<=n;i++)cin>>a[i].y;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        s+=a[i].x;
        //如果选了当前点做贡献，肯定只能从比b小的d转过来
        for(int j=a[i].y;j>=0;j--)
        ans=max(ans,d[j+a[i].y]=max(d[j+a[i].y],d[j]+a[i].x*(a[i].y-1)));
    }
    cout<<ans+s;
}
/*
!(^w^)?
*/