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)。

输入输出格式

输入格式：

第一行一个正整数n，表示物品的个数。

接下来第2行到第n+1行，每行两个正整数Wi和Ri，含义如题目所述。

输出格式：

输出仅一行，表示最大的收益。

输入输出样例

输入样例#1：

输出样例#1：

说明

20%的数据满足：n<=5，0<=Wi,Ri<=1000。

50%的数据满足：n<=15，0<=Wi,Ri<=1000。

100%的数据满足：n<=3000，0<=Wi,Ri<=200000。

样例解释：我们可以选择1号物品，获得了5点收益；之后我们再选择2号物品，获得3-2=1点收益。最后总的收益值为5+1=6。

#include<iostream>

#include<cstdio>

using namespace std;

#define maxn 3010

int n,w[maxn],r[maxn],ans;

bool vis[maxn];

void dfs(int val,int sum){

    ans=max(ans,val);

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

        if(w[i]-sum<=||vis[i])continue;

        vis[i]=;

        dfs(val+w[i]-sum,sum+r[i]);

        vis[i]=;

    }

}

int main(){

    scanf("%d",&n);

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

    dfs(,);

    printf("%d",ans);

    return ;

}

50分纯暴力

/*

    按照Ri从大到小排个序。然后设dp[i][j]表示前i个物品中选j个可以获得的收益最大值。

    状态转移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j-1]+W[i]-R[i]*(j-1)}

    边界条件：dp[1][1]=W[1]

    最后的答案=max{dp[n][i]}

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 3010

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

struct node{

    int w,r;

}a[maxn];

int cmp(node x,node y){

    return x.r>y.r;

}

int main(){

    scanf("%d",&n);

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

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

    dp[][]=a[].w;

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

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

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

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

        ans=max(ans,dp[n][i]);

    printf("%d",ans);

}

100分贪心+dp

收益

洛谷P2647 最大收益

P2647 最大收益

题目描述

输入输出格式

输入输出样例

说明