用的是记忆化搜索，写得应该还是比较好看的。

#include<stdio.h>
#include<iostream>
#define INF 99999999
using namespace std;

struct node
{
	int a,b,cost;
};

node num[150];
int dp[150][150],N,M,K;
bool visit[150][150];

int search(int x,int y,int kk)
{
	if(x==0 && y==0) 
	{
		visit[0][0]=true;
		return 0;
	}
	if(visit[x][y]) return dp[x][y];
	int i,temp,result=INF;
	for(i=0;i<kk;i++)
	{
		if(x-num[i].a<0 || y-num[i].b<0 || x-num[i].a>N || y-num[i].b>M) continue;
		temp=search(x-num[i].a,y-num[i].b,kk);
		if(temp+num[i].cost<result)
			result=temp+num[i].cost;
	}
	dp[x][y]=result;
	visit[x][y]=true;
	return result;
}

int main()
{
	int i,j,ans;
	while(scanf("%d%d%d",&N,&M,&K))
	{
		if(N+M+K==0) break;
		for(i=0;i<K;i++)
			scanf("%d%d%d",&num[i].a,&num[i].b,&num[i].cost);
		for(i=0;i<=N;i++)
			for(j=0;j<=M;j++)
			{
				dp[i][j]=INF;
				visit[i][j]=false;
			}
		ans=search(N,M,K);
		if(ans==INF)
			printf("-1\n");
		else
			printf("%d\n",ans);
	}
	return 0;
}

• Re:谁能帮我看一下代码。简单的DP，已经测了一天的数据，还是WA (54) linandmin 2006-08-28 00:43:04