C语言解答

#include "stdio.h"
int n;
int max,s,e;
int a[201],f[201][201];
void F()
{
	int i;
	if(s==e)
	{
		printf("%d\n",e);
		return ;
	}
	printf("%d-",s,e);
	for(i=s+1;i<=e;i++)
		if(f[s][i]+f[i][e]-a[i]==f[s][e])
		{
			s=i;
			F();
			return;
		}
}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i][i]=a[i];
	}
	scanf("%d%d",&s,&e);
	while(s&&e)
	{
		f[s][e]=a[s]+a[e];
		scanf("%d%d",&s,&e);
	}
	s=e=0;
	for(i=1;i<=n;i++)
	{
		for(j=i;j>0;j--)
		{
			for(k=j;k<=i;k++)
			{
				if(f[j][k]&&f[k][i]&&f[j][i]<f[j][k]+f[k][i]-a[k])
					f[j][i]=f[j][k]+f[k][i]-a[k];
			}
			if(f[j][i]>f[s][e])
				s=j,e=i;
		}
	}
	max=f[s][e];
	F();
	printf("%d\n",max);
	return 0;
}

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[201],b[201],f[201],g[201][201]={0};//f[i]数组表示从第i个地窖起挖 
void init();
void work();
int main()
{
	init();
	work();
	return 0;
} 
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0)break;
		g[x][y]=1;
	}
}
void work()
{
	f[n]=a[n];	
	for(int i=n-1;i>0;i--)
	{
		int my_max=0,k=0;
		for(int j=i+1;j<=n;j++)
		{
			if(g[i][j]&&f[j]>my_max)
			{
				my_max=f[j];
				k=j;			
			}
		}
		f[i]=my_max+a[i];
		//cout<<"i="<<i<<' '<<k<<' '<<f[i]<<endl;
		b[i]=k;
	}
	int tot=0,k=0;
	//for(int i=1;i<=n;i++)cout<<f[i]<<' ';
	for(int i=1;i<=n;i++)if(tot<f[i]){tot=f[i];k=i;}
	cout<<k;
	k=b[k];
	while(k!=0)
	{
		cout<<'-'<<k;
		k=b[k];
	} 
	cout<<endl;
	cout<<tot<<endl;
}