[CCC 2015 S5] Greedy For Pies

Bulyly · 2023-10-30 15:39:46 · 题解

• 原题链接。

• 一道较为直接的 dp。首先我们要清楚 b 数组的作用，显然可以分为以下两类。第一种是用来当炮灰，就是让我们可以选两个 a 中两个连续的数，第二种是用来作为被选择的数。对于 b 中要选的数，我们贪心的选取最大的数，炮灰用最小的显然最优。

• 定义状态 f_{i,j,k,0/1} 表示对于 a 中的前 i 个数，已经用来 j 个 b 数组中的数，其中有 k 个不是炮灰。有如下转移：

  • 不加入 b：

    $f_{i,j,k,1}=f_{i-1,j,k,0}+a_i$。

  • 加入 b：

    要选：f_{i,j,k,0}=\max(f_{i,j,k,0},f_{i-1,j-1,k-1,0+b_{m-k+1}})。

    炮灰：f_{i,j,k,1}=\max(f_{i,j,k,1},f_{i-1,j-1,k,1+a_i})。

• 如果 b 数组没有用完，显然用完一定不劣。所以我们还要对每个没用完 b 的状态继续仿照上面 dp。

Code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=4e3+10;
int n,m,ans,a[N],b[105],f[2][105][105][2];

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    sort(b+1,b+m+1);
    for(int i=1;i<=n;i++) {
        int now=i&1,pre=now^1;
        for(int j=0;j<=m;j++) {
            for(int k=0;k<=j;k++) {
                f[now][j][k][0]=max(f[pre][j][k][1],f[pre][j][k][0]);
                f[now][j][k][1]=f[pre][j][k][0]+a[i];
                if(j&&k) f[now][j][k][0]=max(f[now][j][k][0],f[pre][j-1][k-1][0]+b[m-k+1]);
                if(j-1>=k) f[now][j][k][1]=max(f[now][j][k][1],f[pre][j-1][k][1]+a[i]);
                ans=max({ans,f[now][j][k][0],f[now][j][k][1]});
            } 
        }
    }
    for(int i=n+1;i<=n+m;i++) {
        int now=i&1,pre=now^1;
        for(int j=0;j<=m;j++) {
            for(int k=0;k<=j;k++) {
                if(j) f[now][j][k][0]=max(f[pre][j-1][k][1],f[pre][j-1][k][0]);
                if(j&&k) f[now][j][k][1]=f[pre][j-1][k-1][0]+b[m-k+1];
                ans=max({ans,f[now][j][k][0],f[now][j][k][1]});
            } 
        }
    }
    cout<<ans<<"\n";        
    return 0;
}