Why The Time Limit??
#include <Stdio.h>

#define MAX_N 100000
#define Mu .1e11

int data[101];
float dina[MAX_N][MAX_N];

int main()
{
	FILE *fi;
	fi = stdin;;
	int n,m;
	int i,j;
	int num[MAX_N];
	float prime,price[MAX_N];
	int y;
	while(1){
		fscanf(fi,"%d %d",&n,&m);
		if(n == 0 && m == 0 )break;
		for(i = 0; i < n; i++){
			
			fscanf(fi,"%d",&data[i]);
			
		}
		for(i = 1; i <= m; i++){
			
			fscanf(fi,"%d %f",&num[i],&prime);
			
			price[i] = prime;
			
		}	
		for(i = 0; i <= n; i++){
			for(j = 0; j <= m; j++){
				dina[0][j] = 0;
				dina[i][0] = Mu;
			}
		}
		y = 0;
		for(i = 1; i <= n; i++,y++){
			for(j = 1; j <= m; j++){
				if(data[y] == num[j]){
					if(price[j] + dina[i - 1][j - 1]  > price[j] + dina[i][j - 1])
						dina[i][j] = price[j] + dina[i][j - 1];
					else
						dina[i][j] = price[j] + dina[i - 1][j - 1];
				}else{
					dina[i][j] = dina[i][j - 1];	
				}
			}
		}
		if(dina[n][m] == Mu){
			printf("Impossible\n");
		}else{
			printf("%.2f\n",dina[n][m]);
		}
	}
	return 0;
}

• DP的第2层循环的范围优化下也许就可以了 (1226) daringQQ 2007-01-18 18:46:42