终于又ac了一题.....最近几天我被淹没在绿色的wrong answer里。

『这个题很经典』hysbz的admin如是说。但我还是用不那么经典的办法.....用了两个数组，一个存标志位一个存数据。那个排序可有可无。

#include <cstdio>
#include <string>

int a[100001], b[100001], c, n, mx;
int ni[10], di[10];

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &c) != EOF)
 {
  int i, k, j;
  scanf("%d", &n);
  for(i = 0; i < n; i ++)
  {
   scanf("%d %d", &ni[i], &di[i]);
  }
  for(i = 0; i < n - 1; i ++)
  {
   int j = i, t0 = di[i], t1 = ni[i];
   for(k = i + 1; k < n; k ++)
   {
    if(t0 > di[k])
    {
     j = k; t0 = di[k];
    }
   }
   di[j] = di[i]; di[i] = t0; ni[i] = ni[j]; ni[j] = t1;
  }
  //pt();
  mx = 0;
  memset(a, 0, sizeof(a));
  b[0] = 0;
  int pi = 1, ti; // index for b[]....vector.
  for(i = 0; i < n; i ++)
  {
   ti = pi;
   for(j = 0; j < pi; j ++)
   {
    for(k = 0; k <= ni[i]; k ++)
    {
     int t = b[j] + di[i] * k;
     if(t <= c)
     {
      if(a[t]) continue;
      a[t] = 1;
      b[ti ++] = t;
      if(t == c)
       goto out;
     }
    }
   }
   pi = ti;
  }
out:
  for(i = c; i >= 0; i --)
  {
   if(a[i])
   {
    mx = i;
    break;
   }
  }
  printf("%d\n", mx);
 }
 return 0;
}

评论