[luogu P2647] 最大收益（貪心+dp），luogup2647

[luogu P2647] 最大收益（貪心+dp），luogup2647

題目傳送門：https://www.luogu.org/problem/show?pid=2647

題目描述

現在你面前有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)。

輸入輸出格式

INPUT：

第一行一個正整數n，表示物品的個數。

接下來第2行到第n+1行，每行兩個正整數Wi和Ri，含義如題目所述。

OUTPUT：

輸出僅一行，表示最大的收益。

輸入輸出樣例

   輸入樣例#1：

2
5 2
3 5

輸出樣例#1：

6

//樣例解釋：我們可以選擇1號物品，獲得了5點收益；之後我們再選擇2號物品，獲得3-2=1點收益。最後總的收益值為5+1=6。

說明

　　20%的數據滿足：n<=5，0<=Wi,Ri<=1000。

　　50%的數據滿足：n<=15，0<=Wi,Ri<=1000。

　　100%的數據滿足：n<=3000，0<=Wi,Ri<=200000。

SOLUTION 1：暴力枚舉出每個物品選或不選，生成物品選取順序的全排列，暴力求最優解。時間復雜度O（2^n*n！）。期望得分20分。

SOLUTION 2：不難發現我們可以對題目進行一個等價的轉換，即倒序選取，選取第 i 件物品會使之前所有選取的物品收益減少R_i。

　　　　　　　   由此可以得出貪心策略：首先對所有物品按照R由大到小排序，枚舉每個物品選或不選，求出最優解。

　　　　　　   　時間復雜度O（2^n）。期望得分50分。

SOLUTION 3：受SOL2啟發，我們可以設計一個動態規劃策略，f[i][j] 表示前 i 個物品取 j 個的最大收益，

　　　　　　　　不難發現其狀態轉移方程為：f[i][j]=max(f[i-1][j],f[i-1][j-1]+w[i]-r[i]*(j-1))   ，

　　　　　　　　邊界條件f[1][1]=w[1]  f[1][0]=0  ，其中物品按照R由小到大排序，

　　　　　　　　ans=max(f[n][i]) ，

　　　　　　　　時間復雜度O（n^2），期望得分100分。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct thing {
 7     int a,b;
 8 } e[3050];
 9 
10 bool cmp(const thing x,const thing y) {
11     return x.b>y.b;
12 }
13 
14 int n,ans,f[3005][3005];
15 
16 int main() {
17     scanf("%d",&n);
18     for (int i=1; i<=n; i++) scanf("%d%d",&e[i].a,&e[i].b);
19     sort(e+1,e+n+1,cmp);
20     f[1][0]=0;
21     f[1][1]=e[1].a;
22     for (int i=2; i<=n; i++) {
23         for (int j=1; j<=i; j++)
24             f[i][j]=max(f[i-1][j],f[i-1][j-1]+e[i].a-e[i].b*(j-1));
25     }
26     for (int i=1; i<=n; i++) ans=max(ans,f[n][i]);
27     printf("%d",ans);
28 }