1 条题解

  • -1
    @ 2025-7-4 14:18:16

    在比赛过程中卷whk导致这么唐的一道题没切

    直接把单买的东西也改成套餐,然后因为东西的下标比较多吗,直接离散化,然后五维dp扔上去完全背包

    大家千万不要像我一样把代码写的这么狗屎,还厌氧

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #define N 205
    #define MAXN 2005
    #define int long long
    using namespace std;
    bool Test_MLE_start;
    int _=1,T,B,cnt=0,m;
    int c[N][10],k[N][10],n[N],b[N],ton[MAXN],ned[10],num[10],wp[N],tn[N];
    int dp[10][10][10][10][10];
    struct node{
    	int p[10],w;
    }a[N];
    inline int reads(){
    	char c=getchar();
    	int sum=0,f=1;
    	while(!isdigit(c)){
    		if(c=='-') f=-1;
    		c=getchar();
    	}
    	while(isdigit(c)){
    		sum=(sum<<3)+(sum<<1)+(c^'0');
    		c=getchar();
    	}
    	return sum*f;
    }
    inline void files(){
    	freopen("std.in","r",stdin);
    	freopen("std.out","w",stdout);
    }
    inline void clr(){
    //	Don't forget!
    
    }
    bool Test_MLE_end;
    signed main(){
    //	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
    //	files();
    //	_=reads();
    	while(_--){
    		clr();
    		m=T=reads();
    		for(int i=1;i<=T;i++){
    			n[i]=reads();
    			for(int j=1;j<=n[i];j++){
    				c[i][j]=reads(),k[i][j]=reads();
    				b[++cnt]=c[i][j];
    			}
    			a[i].w=reads();
    		}
    		B=reads();
    		for(int i=1;i<=B;i++) ned[i]=reads(),tn[i]=reads(),wp[i]=reads(),b[++cnt]=ned[i];
    		sort(b+1,b+cnt+1);
    		cnt=unique(b+1,b+cnt+1)-b-1;
    		for(int i=1;i<=cnt;i++) ton[b[i]]=i;
    		for(int i=1;i<=T;i++){
    			for(int j=1;j<=n[i];j++) a[i].p[ton[c[i][j]]]=k[i][j];
    		}
    		for(int i=1;i<=B;i++){
    			a[++m].p[ton[ned[i]]]=1;
    			a[m].w=wp[i];
    			num[ton[ned[i]]]=tn[i];
    		}
    		memset(dp,0x3f,sizeof(dp));
    		dp[0][0][0][0][0]=0;
    		for(int i=1;i<=m;i++){
    			for(int A=0;A<=num[1];A++){
    				for(int B=0;B<=num[2];B++){
    					for(int C=0;C<=num[3];C++){
    						for(int D=0;D<=num[4];D++){
    							for(int E=0;E<=num[5];E++){
    								if(A<a[i].p[1]) continue;
    								if(B<a[i].p[2]) continue;
    								if(C<a[i].p[3]) continue;
    								if(D<a[i].p[4]) continue;
    								if(E<a[i].p[5]) continue;
    								dp[A][B][C][D][E]=min(dp[A][B][C][D][E],dp[A-a[i].p[1]][B-a[i].p[2]][C-a[i].p[3]][D-a[i].p[4]][E-a[i].p[5]]+a[i].w);
    							}
    						}
    					}
    				}
    			}
    		}
    		printf("%lld\n",dp[num[1]][num[2]][num[3]][num[4]][num[5]]);
    	}
    	return 0;
    }
    
    
    • 1

    信息

    ID
    312
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    (无)
    递交数
    34
    已通过
    14
    上传者