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，已经测了一天的数据，还是WA

Posted by linandmin at 2006-08-28 00:35:46 on Problem 2982
```用的是记忆化搜索，写得应该还是比较好看的。

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

Followed by: