【CF808E】 Selling Souvenirs

肖然 · 2019-09-12 13:47:04 · 题解

特殊性质是物品重量只有3种 $w[i]=1/2/3

【算法0】

首先考虑 w[i]=1/2 两种重量，可以各自按 v[i] 大->小排序后贪心，设DP状态：

dp[j] = max(s1[n1] + s2[j-n1])
其中 s1,s2 为排序后 v 的前缀和，n1 = 选多少个 1 物品

再考虑枚举选取 w[i]=3 的物品数量n3 ，就有了一个总复杂度 O(C^2) 的算法。

ans = max(s3[n3] + dp[C-3\times n3])

当然，这个算法不能通过 C = 3\times 10^5 的数据

【算法1】

考虑将dp状态设成一个4元组：

dp[j] = (c,n1,n2,n3)
代表总容量为 j 时的最大价值 c ，同时对应选取了 n1,n2,n3 个 1,2,3 物品

"我为人人"式更新，有三种更新方式：

{c+v1[n1+1],n1+1,n2,n3}\to dp[j+1]
{c+v2[n2+1],n1,n2+1,n3}\to dp[j+2]
{c+v3[n3+1],n1,n2,n3+1}\to dp[j+3]

其中 v1[i],v2[i],v3[i]= 价值第 i 大的1-3物品价值

这样复杂度是 O(3C) 不会TLE，但不幸的是会WA。

例如

Consider the case n=4, m=7 with 4 items
A = (1,3)
B1 = B2 = (2,4)
C = (3,6)

Then the (only) optimal solution
dp[4] = A + C
dp[5] = A + B1 + B2
dp[6] = A + B1/B2 + C
dp[7] = B1 + B2 + C

but there is no way to create the solution for dp[7] by adding items to any of the three solutions before.
(https://codeforces.com/blog/entry/52010?#comment-360499)：

幸运的是我们可以修正这个算法，考虑第4种转移：

c-v1[n1]+v3[n3+1],n1-1,n2,n3+1 \to dp[j+2]

即拿走一个 1 物品添上一个 3 物品，这样 dp[7] 就能从 dp[5] 转移过来，可以AC本题。

#include <bits/stdc++.h>
#define MAXN 300005
#define LL long long
using namespace std;

struct Node{
    LL c;
    int n1, n2, n3;
    Node(LL c=0, int n1=0, int n2=0, int n3=0):c(c), n1(n1), n2(n2), n3(n3){}
} dp[MAXN];
int N,M;
int v[4][MAXN];
int cnt[4];

void update(Node& a, Node b){
    if(a.c < b.c) a = b;
} 

int main() {
    cin>>N>>M;
    for(int i=1;i<=N;i++) {
        int w,x;
        cin>>w>>x;
        v[w][++cnt[w]] = x;
    }

    for(int w=1;w<=3;w++){
        sort(v[w]+1, v[w]+1+cnt[w], greater<int>());
    }

    dp[0] = Node(0,0,0,0);
    LL ans = 0;
    for(int j=0;j<=M;j++){
        LL c = dp[j].c;
        int n1 = dp[j].n1, n2 = dp[j].n2, n3 = dp[j].n3;
        if(j+1<=M && n1 < cnt[1]) update(dp[j+1], Node(c+v[1][n1+1], n1+1, n2, n3));
        if(j+2<=M && n2 < cnt[2]) update(dp[j+2], Node(c+v[2][n2+1], n1, n2+1, n3));
        if(j+3<=M && n3 < cnt[3]) update(dp[j+3], Node(c+v[3][n3+1], n1, n2, n3+1));

        if(j+2<=M && n1 && n3 < cnt[3]) update(dp[j+2], Node(c-v[1][n1]+v[3][n3+1], n1-1, n2, n3+1));

        ans = max(ans, c);
    }
    cout<<ans<<endl;
    return 0;
}

【算法2】

假设只考虑 w[i]=2/3 两种物品，同样可以各自按 v[i] 大->小排序后贪心，枚举 n3 可以在 O(N) 时间内计算答案：

ans = max(s3[n3] + s2[(M-3\times n3)/2])

那么怎么考虑 w[i]=1 的物品呢？

考虑分类讨论：

最优解取了偶数个 1 物品，那么将所有 1 物品排序后两两打包，视为n1/2 个 2 物品即可；
最优解取了奇数个 1 物品，那么必取价值最大的那个 1 物品，剩下的 1 物品两两打包视为 2 物品即可；

最后2种情况取max，总复杂度 O(N)。

#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long
using namespace std;

int N,C;
vector<int> Adj[4];
vector<int> v2;
int n1,n2,n3;

LL s[4][MAXN];
LL ans1,ans2;

void calS2(){
    sort(v2.begin(), v2.end(), greater<int>());
    for(int i=0;i<v2.size();i++){
        s[2][i+1] = s[2][i] + v2[i];
    }
    return;
}

int main(){
    cin>>N>>C;

    int w,v;
    for(int i=1;i<=N;i++){
        cin>>w>>v;
        Adj[w].push_back(v);
    }

    //sort3
    sort(Adj[3].begin(), Adj[3].end(), greater<int>());
    for(int i=0;i<Adj[3].size();i++){
        s[3][i+1] = s[3][i] + Adj[3][i];
    }

    //even
    sort(Adj[1].begin(), Adj[1].end(), greater<int>());
    for(int i=1;i<Adj[1].size();i+=2){
        v2.push_back(Adj[1][i] + Adj[1][i-1]);
    }
    for(int i=0;i<Adj[2].size();i++){
        v2.push_back(Adj[2][i]);
    }
    calS2();
    for(n3=0;n3<=Adj[3].size();n3++){
        if(C-3*n3 < 0) continue;
        n2 = min((C-3*n3)/2, int(v2.size()));
        ans1 = max(ans1, s[3][n3] + s[2][n2]);
    }
    if(Adj[1].size()==0){
        cout<<ans1<<endl;
        return 0;
    }

    //odd
    sort(Adj[1].begin(), Adj[1].end(), greater<int>());
    v2.clear();
    for(int i=2;i<Adj[1].size();i+=2){
        v2.push_back(Adj[1][i] + Adj[1][i-1]);
    }
    for(int i=0;i<Adj[2].size();i++){
        v2.push_back(Adj[2][i]);
    }

    calS2();
    for(n3=0;n3<=Adj[3].size();n3++){
        if(C-3*n3-1 < 0) continue;
        n2 = min((C-3*n3-1)/2, int(v2.size()));
        ans2 = max(ans2, s[3][n3] + s[2][n2] + Adj[1][0]);
    }
    cout<<max(ans1, ans2);
    return 0;
}