1 条题解
-
-1
在比赛过程中卷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
- 上传者