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

## 因为a可以等于0，而b可以取负数，所以行列顺序dp是错的

Posted by liangzhirong at 2006-09-03 23:21:02 on Problem 2982
In Reply To:老是WA,牛人解惑!! Posted by:kkkk at 2006-08-29 17:22:41
```> #include <iostream>
> using namespace std;
> int a[100][3];
> int b[100][100];
> int N,M,k;
> int Minmoney(int disN,int disM,int ttN,int ttM);//用来求到达(disN,disM)需要最少money
> int main()
> {
> cin>>N>>M>>k;
> int minN,minM;
>
> while(N||M||k)
> {minN=100;
> minM=100;
> 	for(int i=0;i<k;i++)
> 	{cin>>a[i][0]>>a[i][1]>>a[i][2];
>     if(a[i][0]<minN)
> 		minN=a[i][0];
> 	if(a[i][1]<minM)
> 		minM=a[i][1];
> 	}
> 	b[N][M]=20000;
> for(i=0;i<=N;i++)
>  for(int t=0;t<=M;t++)
> b[i][t]=Minmoney(i,t,minN,minM);//求到达(i,t)点所需要最少money
> if(b[N][M]<20000)
> cout<<b[N][M]<<endl;
> else cout<<-1<<endl;
> cin>>N>>M>>k;
> }
> return 0;}
> int Minmoney(int disN,int disM,int ttN,int ttM)
> {int j;
> int tmp;
> int min=20000;
> if(disN==0&&disM==0)
> 	return 0;
> if((disN<ttN&&disN!=0)||(disM!=0&&disM<ttM))
> 	return 20000;
> else
> 	{for(j=0;j<k;j++)
> 		{if(a[j][0]>disN||a[j][1]>disM)
> 		continue;
> 		tmp=b[disN-a[j][0]][disM-a[j][1]]+a[j][2];
> 		if(tmp<min)
> 		min=tmp;
> 		}
> 		return min;
> 	}
>
> }
```

Followed by: