rqnoj/6.c

   1 #include <stdio.h>
   2
   3 #define max_value 200010
   4 #define maxn 100
   5
   6 int max(int p, int q) {
   7         return p>q?p:q;
   8 }
   9
  10 int main() {
  11         int money,n;
  12         scanf("%d%d",&money,&n);
  13         money/=10;
  14         int f[max_value]={0},v[maxn],p[maxn],q[maxn],q1[maxn],q2[maxn];
  15         int i,j;
  16         for (i=1; i<=n; i++) {
  17                 scanf("%d%d%d",&(v[i]),&(p[i]),&(q[i]));
  18                 v[i]/=10;
  19                 q2[q[i]]=q1[q[i]];
  20                 q1[q[i]]=i;
  21         }
  22         f[0]=1;
  23         int ans=0;
  24         for (j=1; j<=n; j++)
  25                 if (q[j]==0)
  26                         for (i=money; i>=v[j]; i--) {
  27                                 if (i-v[j]>=0) f[i]=max(f[i],f[i-v[j]]+v[j]*p[j]);
  28                                 if (i-v[j]-v[q1[j]]>=0) f[i]=max(f[i],f[i-v[j]-v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]);
  29                                 if (i-v[j]-v[q2[j]]>=0) f[i]=max(f[i],f[i-v[j]-v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[j]]);
  30                                 if (i-v[j]-v[q1[j]]-v[q2[j]]>=0) f[i]=max(f[i],f[i-v[j]-v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]+v[q2[j]]*p[q2[j]]);
  31                                 ans=max(ans,f[i]);
  32                         }
  33         printf("%d\n",(--ans)*10);
  34         return 0;
  35 }