又有问题啦 [复制链接]

挖地雷
Time Limit:1000MS  Memory Limit:65536K


Description

在一条河堤上有若个个地雷坑。每个地雷坑中埋有一定数量的地雷，地雷坑的编号为1，2，3，…，n(n≤3000)。同时在每个地雷坑中都有一张说明书（除最后一个地雷坑外），在挖完此坑后，还可以继续挖哪些坑编号大于该坑编号的坑，即：如果从编号X挖，再挖编号Y,则一定Y大于X。找出一种挖地雷的方法，能一次挖的地雷最多。

Input

第一行一个数n；第二行为n个正整数，每个正整数用一个空格隔开，每个数小于1000；后面若干行，每行两个正整数X和Y（用一个空格隔开），表示挖完第X个坑后可以挖第Y个坑，最后两个数若为零，表示结束。

Output

一行，最多的地雷数。

Sample Input


10
8 14 2 17 33 26 15 17 19 6
1 2
1 4
1 5
1 7
2 3
2 5
2 6
4 5
4 6
5 6
5 7
5 8
6 8
6 9
7 8
7 9
7 10
8 9
8 10
0 0

Sample Output


120

和"过河"差不多,最少改最多就行了

如果输入数据是有序的（即给出的说明书是从小到大的）
就不考虑哈希的空间问题了，给出代码如下（已经检测，可以过Sample）
具体怎么解决hash的空间问题，我认为得用到指针
#include<fstream>
using namespace std;
ifstream fin("wadilei.in");
ofstream fout("wadilei.out");
int main()
{
  int i,j,k;
  int a[3010],d[3010];
  int n;
  int *p;
  memset(d,0,sizeof(d));
  fin>>n;
  for(i=1;i<=n;i++)
  fin>>a;
  d[1]=a[1];
  while(1)
  {
  fin>>j>>k;
  if(j==0&&k==0)break;
  if(d[j]+a[k]>d[k])
  d[k]=d[j]+a[k];
  } 
  k=-1;
  for(i=1;i<=n;i++)
  if(d>k)
  k=d;
  fout<<k<<endl;
  return 0;
}

#include<fstream>
using namespace std;
ifstream fin("wadilei.in");
ofstream fout("wadilei.out");
int main()
{
  int i,j,k;
  int a[3010],d[3010];
  int n;
  int *p;
  memset(d,0,sizeof(d));
  fin>>n;
  for(i=1;i<=n;i++)
  fin>>a;
  d[1]=a[1];
  while(1)
  {
  fin>>j>>k;
  if(j==0&&k==0)break;
  if(d[j]+a[k]>d[k])
  d[k]=d[j]+a[k];
  } 
  k=-1;
  for(i=1;i<=n;i++)
  if(d>k)
  k=d;
  fout<<k<<endl;
  return 0;
}

sorry，很奇怪，最后部分的[i]都被过滤了，不过你应该能看懂吧！