CF366C题解

· · 题解

题目链接：Link

 

题目大意：

给定长度为 n 的两个序列 a 和 b 和一个不大于 10 的正整数 k，选出若干个下标 i 组成集合 X，使得\sum\limits_{i=1}^{i\in X}a_i=k\times \sum\limits_{i=1}^{i\in X}b_i，求满足这个条件时 \sum\limits_{i=1}^{i\in X}a_i 的最大值。

解题思路：

看到常规写法题解区已经有很多了，这里提供一种略微有些抽象的实现方式。

先讲讲思路，题目一眼 dp，于是开始看数据范围猜测一下时间复杂度，发现 1 \leq n,a_i,b_i\leq 100，1 \leq k \leq 10，比较小，一看就是给我这种乱搞选手准备的（bushi）。

于是开始观察题面，准备找一些可以乱搞的性质。发现对于 x \equiv z\pmod{m} 和 y\equiv m-z\pmod{m}，x+y\equiv 0\pmod{m}，于是我们显然可以将序列分为 a_i-k\times b_i>0，这里称为 pst，和 a_i-k\times b_i<0，这里称为 neg，两部分进行处理，而对于等于零的那部分，显然会被选择，于是输入的时候直接添加到答案中即可， 然后又因为 a_i,b_i\leq100，k\leq10，所以在最极端的情况下 |a_i-k\times b_i|=999，这时 a_i=1， b_i=100，k=10。假设对于所有的 i \in [1,n]，|a_i-k\times b_i|=999，那么任意从中选取若干个下标 i 组成集合 X，\sum\limits_{i=1}^{i\in X}|a_i-k\times b_i| \leq99900，这是显然的。

可以发现最大值并不是不可接受，于是便考虑使用一种极度抽象的做法，也就是对于序列 pst 和 neg，枚举出所有的可能的 \sum\limits_{i=1}^{i\in X}|a_i-k\times b_i|，之后对于每个可能值，记录其最大的 \sum\limits_{i=1}^{i\in X}a_i。

然后我们尝试对于两个序列进行配对，也就是枚举由 pst 序列中的元素能构造出的和，判断 neg 序列是否也能构造，如果可以就计算出两个序列中这个和所对应的最大值之和，这里记为 sum，这些 sum 的最大值，即为最终的答案。

枚举可能和不难实现，这里记一个数组 stk，和一个数组 deli，代表 pst 中的元素能够造出的可能和和每个可能和所对应的最大 a_i 之和，假设现在枚举到 pst_i，而 stk 数组中已经记录了x 个可能和，那么我们尝试枚举 i \in [1,x]，并判断 deli[stk[i]+pst[j]] 是否已经赋值，如果未赋值则 stk[i]+pst[j] 一定为一个未出现过的可能和，将其记录到 stk 中并给对应的 deli 赋值，而如果则有值，则判断是否能增大 deli[stk[i]+pst[j]] 的值。

配对也比较容易实现，这里不再多赘述，详细可以看代码。

代码如下：

#include<bits/stdc++.h>
#define lson pos<<1
#define rson pos<<1|1
#define ll long long
using namespace std;
const int maxn=1e2+10;
const ll mod=998244353;
int n,m,k;
int a[maxn],b[maxn];
int neg[maxn],pst[maxn];
int neg1[maxn],pst1[maxn];
int cnt1=0,cnt2=0;
int deli[100010],deli1[100010];
int stk[100010],stk1[100010];
struct node{
    int id,sum;
}q[100010];

int main(){
    //freopen("test.in","r",stdin);
    //freopen("wjudge.out","w",stdout);
    memset(deli,0,sizeof(deli));
    memset(deli1,0,sizeof(deli1));
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }

    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        if(b[i]*m<a[i]) pst[++cnt1]=a[i]-b[i]*m,pst1[cnt1]=a[i];//分为不同的序列
        else if(b[i]*m==a[i]) ans+=a[i];
        else neg[++cnt2]=b[i]*m-a[i],neg1[cnt2]=a[i];  
    }

    stk[0]=stk1[0]=0;
    int tp=0,tp1=0;
    for(int i=1;i<=cnt1;i++){
    //  cout<<pst[i]<<" ";
        int r=0;
        int tmp=tp;//这里防止单个数重复计算
        for(int j=0;j<=tmp;j++){
            //if(stk[j]+pst[i]==) cout<<endl<<stk[j]<<" "<<pst[i]<<endl;
            if(deli[stk[j]+pst[i]]){//如果已经出现过这个和则更新最大值
                if(deli[stk[j]+pst[i]]<deli[stk[j]]+pst1[i]){
                    q[++r].id=stk[j]+pst[i];
                    q[r].sum=deli[stk[j]]+pst1[i];
                }
            }
            else{//没有出现就把新的和推进来
                stk[++tp]=stk[j]+pst[i];
                if(deli[stk[j]+pst[i]]<deli[stk[j]]+pst1[i]){
                    q[++r].id=stk[j]+pst[i];
                    q[r].sum=deli[stk[j]]+pst1[i];
                }
            }
        }

        for(int j=1;j<=r;j++) deli[q[j].id]=q[j].sum;
    }
    //cout<<deli[408]<<endl;

    for(int i=1;i<=cnt2;i++){
    //  cout<<neg[i]<<"  ";
        int r=0;
        int tmp=tp1;
        for(int j=0;j<=tmp;j++){
        //  if(stk1[j]+neg[i]==342)cout<<endl<<stk1[j]<<" "<<neg[i]<<endl;
            if(deli1[stk1[j]+neg[i]]){
                if(deli1[stk1[j]+neg[i]]<deli1[stk1[j]]+neg1[i]){
                    q[++r].id=stk1[j]+neg[i];
                    q[r].sum=deli1[stk1[j]]+neg1[i];
                }
            }
            else{
                stk1[++tp1]=stk1[j]+neg[i];
                if(deli1[stk1[j]+neg[i]]<deli1[stk1[j]]+neg1[i]){
                    q[++r].id=stk1[j]+neg[i];
                    q[r].sum=deli1[stk1[j]]+neg1[i];
                }
            }
        }

        for(int j=1;j<=r;j++) deli1[q[j].id]=q[j].sum;
    }

    int tmp=0;
    for(int i=1;i<=tp;i++){//配对
        if(deli1[stk[i]]) tmp=max(tmp,deli[stk[i]]+deli1[stk[i]]);//判断stk中出现的数在stk1中是否也出现过
    }
    //cout<<endl;

    if(ans==0&&tmp==0) printf("-1");//是否有解
    else printf("%d",tmp+ans);
    return 0;
}

完结撒花 OvO！！！