#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;
	}

}

• 因为a可以等于0，而b可以取负数，所以行列顺序dp是错的 (1058) liangzhirong 2006-09-03 23:21:02