2044.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2044 on 2005-12-24 at 22:06:36 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 128;
const double INF = 2e9;
const double eps = 1e-3;

int main()
{
	int list[MAX];
	double low[MAX], p;
	int n, m, k, i, j;
	
	low[0] = 0;
	while(scanf("%d %d", &n, &m) != EOF && n*m != 0) {
		for(i = 1; i <= n; i++) {
			scanf("%d", &list[i]);
			low[i] = INF;
		}
		for(i = 1; i <= m; i++) {
			scanf("%d %lf", &k, &p);
			for(j = min(i, n); j >= 1; j--) {
				if(i == 1) {
					if(k == list[j]) low[j] = p;
					else low[j] = INF;
				} else {
					if(k == list[j]) low[j] = min(low[j-1]+p, low[j]);
				}
			}
		}
		if(fabs(low[n]-INF) < eps) printf("Impossible\n");
		else printf("%.2lf\n", low[n]);
	}
	
	return 0;
}