rqnoj/15.c

   1 #include <stdio.h>
   2
   3 #define maxn 110
   4 #define max_time 1010
   5
   6 int max(int p, int q) {
   7         return p>q?p:q;
   8 }
   9
  10 int main() {
  11         int total_time,n;
  12         scanf("%d%d",&total_time,&n);
  13         int i,j,time[maxn],value[maxn],f[max_time]={0};
  14         for (i=1; i<=n; i++) scanf("%d%d",&(time[i]),&(value[i]));
  15         for (i=1; i<=n; i++)
  16                 for (j=total_time; j>=time[i]; j--)
  17                         f[j]=max(f[j],f[j-time[i]]+value[i]);
  18         int ans=0;
  19         for (i=0; i<=total_time; i++) ans=max(ans,f[i]);
  20         printf("%d\n",ans);
  21         return 0;
  22 }