1999291 2006-08-04 22:51:44 Accepted 1366 C++ 00:01.23 1176K St.Crux 终于又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;}    

评论