rqnoj/57.c

   1 #include <stdio.h>
   2
   3 #define maxn 110
   4
   5 int main() {
   6         int rmb[maxn],rp[maxn],t[maxn];
   7         int f[maxn][maxn],g[maxn][maxn];
   8         int n,i,j,k;
   9         scanf("%d",&n);
  10         for (i=1; i<=n; i++) scanf("%d%d%d",&(rmb[i]),&(rp[i]),&(t[i]));
  11         int m,r; //m->rmb, r->rp
  12         scanf("%d%d",&m,&r);
  13         for (i=1; i<=n; i++)
  14                 for (j=m; j>=rmb[i]; j--)
  15                         for (k=r; k>=rp[i]; k--)
  16                                 if (f[j-rmb[i]][k-rp[i]]+1>f[j][k]) {
  17                                         f[j][k]=f[j-rmb[i]][k-rp[i]]+1;
  18                                         g[j][k]=g[j-rmb[i]][k-rp[i]]+t[i];
  19                                 }
  20                                 else if (f[j-rmb[i]][k-rp[i]]+1==f[j][k] && g[j-rmb[i]][k-rp[i]]+t[i]<g[j][k])
  21                                         g[j][k]=g[j-rmb[i]][k-rp[i]]+t[i];
  22         int ans=-1,anstime;
  23         for (i=1; i<=m; i++)
  24                 for (j=1; j<=r; j++)
  25                         if ((f[i][j]>ans) || (f[i][j]==ans && g[i][j]<anstime)) {
  26                                 ans=f[i][j];
  27                                 anstime=g[i][j];
  28                         }
  29         printf("%d\n",anstime);
  30 }