洛谷 P2647 最大收益

我是题面

恩，贪心，鉴定完毕。

一个物品是否放进来，取决于它是否能对答案做出贡献。

那物品i的贡献就是\(w[i]-r[i]\)

可是收益的减少是会叠加的

那就是\(w[i]-j*r[i]\)，j表示选择物品i后又选择的物品数量

可是我怎么知道选择i后又会选择几件物品啊

那么我们引入一个新的值\(d[i]=w[i]/r[i]\)，表示若使物品i对答案有贡献，选择物品i后最多再选择d件物品

既然这样，我们也有点眉目了，dfs啊

很好，写的很漂亮，50。。。TLE

dfs

看来是不能再优化了

那让我们退回去，往前看“可是我怎么知道选择i后又会选择几种物品啊”

好像有一种方法可以知道还会再选几件，没错，你是不是也想到了，就是 dfs 动规

我们用\(f[i][j]\)表示在前i种物品中选择j件，可是这怎么记忆之前所说的j呢？

还记得之前说好的贪心吗，这里继续贪。

我们把物品按照r从大到小的顺序排序，\(f[i][j]\)表示i件物品选择j件且最先选择j件时的收益

这里的贪心很好证明，既然r要取多次，那么我们自然默认让更小的r选择更多的次数

下面是代码

dfs版

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc() getchar()

#define maxn 3005

using namespace std;

inline ll read(){

    ll a=0;int f=0;char p=gc();

    while(!isdigit(p)){f|=p=='-';p=gc();}

    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

    return f?-a:a;

}

void write(ll a){

    if(a>9)write(a/10);

    putchar(a%10+'0');

}

int n;

struct ahaha{

    int w,r,d;

    friend bool operator < (ahaha x,ahaha y){

        return x.d>y.d;

    }

}a[maxn];

bool c[maxn];    //表示物品是否被选择过

int ans;

inline int max(int x,int y){return x>y?x:y;}

inline int min(int x,int y){return x<y?x:y;}

void dfs(int sum,int sr,int sy){   //sum表示当前收益，sr表示需要累计下去的r，sy表示最多还能选择sy个数贪心就不优了

    ans=max(ans,sum);    //因为不知道选多少个数，所以ans每步比较

    if(!sy)return;    //如果不能再选 返回

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

        if(c[i])continue;

        c[i]=1;

        dfs(sum+a[i].w-sr,sr+a[i].r,min(sy-1,a[i].d));   //sy应取最小值

        c[i]=0;

    }

}

inline void solve(){

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

        c[i]=1;

        dfs(a[i].w,a[i].r,a[i].d);

        c[i]=0;

    }

}

int main(){

    n=read();

    for(int i=1;i<=n;++i)a[i].w=read(),a[i].r=read(),a[i].d=a[i].w/a[i].r;

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

    solve();

    write(ans);

    return 0;

}

DP版

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc() getchar()

#define maxn 3005

using namespace std;

inline ll read(){

    ll a=0;int f=0;char p=gc();

    while(!isdigit(p)){f|=p=='-';p=gc();}

    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

    return f?-a:a;

}

void write(ll a){

    if(a>9)write(a/10);

    putchar(a%10+'0');

}

int n,f[maxn][maxn],ans;

struct ahaha{

    int w,r;

    friend bool operator < (ahaha x,ahaha y){

        return x.r>y.r;

    }

}a[maxn];

int main(){

    n=read();

    for(int i=1;i<=n;++i)a[i].w=read(),a[i].r=read();

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

    f[1][1]=a[1].w;

    for(int i=2;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));    //表示选择i个物品时，选择物品i和不选物品i两种操作

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

    write(ans);

    return 0;

}

巴特西

洛谷 P2647 最大收益

dfs版

DP版

最新文章

热门文章