怎么不玩方人

鉴定完毕：舟p

与同系列的上一道题一样，只是变成了抢商店，所以在经过每个商店的时候记录 f2[m]

需要注意的是，f2[m]只需要在商店内转移

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define str string
#define db double
#define F(n) for(int i=1;i<=n;i++)

const int dx[5]={0,1,-1,0,0};
const int dy[5]={0,0,0,1,-1};

const int LXB=2e5+10;


int n,m,k,t;
int f[LXB],f2[LXB],sum[LXB];
string ss;
char p;

struct node
{
    int w,v,x;
}a[LXB];

bool cmp(node l,node r){return l.x==r.x?l.w<r.w:l.x<r.x;}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T=1;
    while(T--){
        cin>>n>>m;
        F(n){
            cin>>a[i].w>>a[i].v>>a[i].x;
            sum[a[i].x]+=a[i].v;
        }
        sort(a+1,a+1+n,cmp);
        F(n){
            t++,k=a[i].x;
            f2[t]=max(f2[t-1],f[m]+sum[k]);
            sum[k]=0;
            for(int j=m;j>=a[i].w;j--){
                f[j]=max(f[j],f[j-a[i].w]+a[i].v);
            }
        }
    }
    cout<<f2[n];
    return 0;
}