2003120 2006-08-06 15:30:49 Accepted 1524 C++ 00:00.27 400K St.Crux 这个题是典型的dp。n = 100, m = 100000，一开始打算对m进行dp，结果显然超时。后来看了几个帖子，明白是对n进行dp，以每一步的总和为状态转移，方程如下： p(N) = min(p(N - 1) + di, p(N))           p(N) ≠ 0              di                                                p(N) = 0 #include <cstdio>#include <string> double a[100];int b[100], n, m, mx, tmx; int main(){ int i, k; //freopen("in.txt", "r", stdin); while(scanf("%d %d", &n, &m) && n) {  memset(a, 0, sizeof(a));  for(i = 0; i < n; i ++)  {   scanf("%d", &b[i]);  }  mx = 0, tmx = mx;  for(i = 0; i < m; i ++)  {   int ti; double td;   scanf("%d %lf", &ti, &td);   mx = tmx;   for(k = mx; k >= 0; k --)   {    if(ti == b[k])    {     if(a[k] == 0 || a[k - 1] + td < a[k])     {      a[k] = td + a[k - 1];      if(k == mx && mx < n - 1)       tmx = mx + 1;     }    }   }  }  if(a[n - 1] != 0)   printf("%0.2f\n", a[n - 1]);  else   printf("Impossible\n"); } return 0;}

评论