Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## DP的第2层循环的范围优化下也许就可以了

Posted by daringQQ at 2007-01-18 18:46:42 on Problem 1297
```> 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;
> }
>
>
>
>
>
>
>
```

Followed by: