这个题是典型的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;
}

评论