#include "iostream.h"
#include "make2db.h"
#include "fstream.h"

int **s;
double **w,**m;

//非遞歸

void obst(double *a,double *b,int n,double **m,int **s,double **w)
{
	int i1,j1;
	for(int i=0;i<=n;i++)
	{
		w[i+1][i]=a[i];
		m[i+1][i]=0;
		s[i+1][i]=0;
	}
	for(int r=0;r<n;r++)
		for(int i=1;i<=n-r;i++)
		{
			int j=i+r;
			i1=s[i][j-1]>i?s[i][j-1]:i;
			j1=s[i+1][j]>i?s[i+1][j]:j;
			w[i][j]=w[i][j-1]+a[j]+b[j];
			m[i][j]=m[i][i1-1]+m[i1+1][j];
			s[i][j]=i1;
			for(int k=i1+1;k<=j1;k++)
			{
				double t=m[i][k+1]+m[k+1][j];
				if(t<=m[i][j])
				{
					m[i][j]=t;
					s[i][j]=k;
				}
			}
			m[i][j]+=w[i][j];
		}
}

/*void obst(double *a,double *b,int n,double **m,int **s,double **w)
{
	for(int i=0;i<=n;i++)
	{
		w[i+1][i]=a[i];
		m[i+1][i]=0;
	}
	for(int r=0;r<n;r++)
		for(int i=1;i<=n-r;i++)
		{
			int j=i+r;
			w[i][j]=w[i][j-1]+a[j]+b[j];
			m[i][j]=m[i+1][j];
			s[i][j]=i;
			for(int k=i+1;k<=j;k++)
			{
				double t=m[i][k-1]+m[k+1][j];
				if(t<m[i][j])
				{
					m[i][j]=t;
					s[i][j]=k;
				}
			}
			m[i][j]+=w[i][j];
		}
}

//遞歸

double obst(double *a,double *b,int i,int j)
{
	if(m[i][j]>=0)
		return m[i][j];
	if(j==i-1)
	{
		w[i][j]=a[i];
		m[i][j]=0;
		return m[i][j];
	}
	w[i][j]=w[i][j-1]+a[j]+b[j];
	m[i][j]=obst(a,b,i+1,j);
	s[i][j]=i;
	for(int k=i+1;k<=j;k++)
	{
		double t=obst(a,b,i,k-1)+obst(a,b,k+1,j);
		if(t<m[i][j])
		{
			m[i][j]=t;
			s[i][j]=k;
		}
	}
	m[i][j]+=w[i][j];
	return m[i][j];
}*/

void traceback(int i,int j,int **s)
{
	if(i-1==j)
		return;
	traceback(i,s[i][j]-1,s);
	traceback(s[i][j]+1,j,s);
	cout<<s[i][j]<<ends;
}

void main()
{
	int n;
	double *a,*b;
	int k=5;
	ifstream fin("data.txt");
	fin>>n;
	make2DArray(w,n+2,n+2);
	make2DArray(m,n+2,n+2);
	make2DArray(s,n+2,n+2);
	a=new double [n+1];
	b=new double [n+1];
    for(int i=0;i<n;i++)
		fin>>a[i]>>b[i];
	for(int l=0;l<n;l++)
		for(int i=0;i<n;i++)
			m[l][i]=0;
	for(int j=0;j<n;j++)
		for(int i=0;i<n;i++)
			s[i][j]=0;
	obst(a,b,n,m,s,w);
	//obst(a,b,1,n);
	cout<<"最優(yōu)的搜索路徑："<<endl;
	traceback(1,n,s);
	cout<<endl;
}