题解 P3985 【不开心的金明】

· · 题解

我做这道题的思路是模拟链表储存，把v值一样的放入一个链中，并且把链按照不严格递减排列

这道题很简单

...然而我换了3种做法

可以很简单的证明，如果取v一样的，取p最大的一定是最优解

如果要取第n个，为保证最优，必取前面的所有数

剩下的就是###baoli###了（因为只有100个数，通过计算可以得到计算次数不会超过2500次，不会超时）

我的方法主要是针对比较大的情况

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct data{
    int p;
    int v;
}a[101];
struct list{
    int len;
    int sum_p[101];
    int sum_v[101];
}b[101];
int FIND(list &A,list &B,list &C,list &D,int rest);
int n,W,maxn=0;
inline bool cmp(data n1,data n2){
    if(n1.v==n2.v) return n1.p>n2.p;
    else return n1.v<n2.v;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>W;
    int i,j;
    for(i=1;i<=n;++i)
        cin>>a[i].v>>a[i].p;
    sort(a+1,a+n+1,cmp);
    a[0].v=a[1].v;
    memset(b,0,sizeof(b));
    int pos=0;
    for(i=1,j=1;i<=n;++i){
    if(a[i].v!=a[i-1].v) {
        b[j].len=i-pos-1;
        pos=i-1;
        j++;}
        b[j].sum_p[i-pos]=b[j].sum_p[i-1-pos]+a[i].p;
        b[j].sum_v[i-pos]=b[j].sum_v[i-1-pos]+a[i].v;
    if(i==n){
        b[j].len=i-pos;
    }
    }
    int list_num=j;

这上面是模拟链表，注意pos记录开始位置-1，前缀和减少后面的运算，后面是搜索

    for(i=1;i<=list_num;++i){
    FIND(b[i],b[i+1],b[i+2],b[i+3],W);
    }
    cout<<maxn;
return 0;
}
//这里用&A来减少调用函数的复制数组时间和空间，参数rest其实可以不要，我只是第一遍写的时候想错了
int FIND(list &A,list &B,list &C,list &D,int rest){
    int i,j,h,l;
    for(i=0;i<=A.len;++i){
        for(j=0;j<=B.len;++j){
            for(h=0;h<=C.len;++h){
                for(l=0;l<=D.len;++l){
                    if(A.sum_v[i]+B.sum_v[j]+C.sum_v[h]+D.sum_v[l]>rest) break;
                    if(j!=0&&B.sum_v[1]-A.sum_v[1]>3) break;
                    if(h!=0&&C.sum_v[1]-A.sum_v[1]>3) break;
                    if(l!=0&&D.sum_v[1]-A.sum_v[1]>3) break;
//所有不成立的情况需要跳过，由于sum递增，所以后面的数不用考虑，直接break；
//只要成立就要枚举；
                    maxn=max(maxn,A.sum_p[i]+B.sum_p[j]+C.sum_p[h]+D.sum_p[l]);
                }
            }
        }
    }
    return maxn;
}