一直没有注意到原来酋长不是部落等级最高的人呢！！！wa了３次
于是乎，再记录两个状态，记录当前已经发现的最小等级，以及当前已经发现的最大等级，ａｃ也！每次枚举下层状态，注意可交易范围在ｍａｘ－Ｍ，ｍｉｎ＋Ｍ，之间即可。

#include<stdio.h>
#include<stdlib.h>
struct gift
{
   int p;
   int cost;
   int pnum;
   int pcost[101];    
   int phao[101];
}gi[101];
int M,N;
int rec[101][101][101];
int i,j;
int dp(int i,int maxM,int minM)
{
        if(rec[i][maxM][minM]) return rec[i][maxM][minM];
        int temp;
        rec[i][maxM][minM] = gi[i].cost;
        for(int j = 1;j <= gi[i].pnum;j++)
        {
              if(gi[gi[i].phao[j]].p >= maxM - M && gi[gi[i].phao[j]].p <= minM + M 
              && rec[i][maxM][minM] > (temp = dp(gi[i].phao[j],
                                          gi[gi[i].phao[j]].p > maxM ? gi[gi[i].phao[j]].p:maxM,
                                          gi[gi[i].phao[j]].p < minM ? gi[gi[i].phao[j]].p:minM) + gi[i].pcost[j]))
              rec[i][maxM][minM] = temp;
        }
        return rec[i][maxM][minM];
}
int main()
{
    freopen("1062.in","r",stdin);
    freopen("1062.out","w",stdout);
    scanf("%d%d",&M,&N);
    for(i = 1;i <= N;i++)
    {
         scanf("%d%d%d",&gi[i].cost,&gi[i].p,&gi[i].pnum);
         for(j = 1;j <= gi[i].pnum;j++)
         {
              scanf("%d%d",&gi[i].phao[j],&gi[i].pcost[j]);
         }
    }
    printf("%d",dp(1,gi[1].p,gi[1].p));
    return 0;
}

• Re:ac代码——用动归做的（３维） (23) NUAA_040930114 2010-08-03 20:32:14