tangle.cpp

来自「数字三角形问题,使用动态规划算法解决问题,包含输入输出文件」· C++ 代码 · 共 78 行

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>

void main()
{
	ifstream fin("input.txt");
	ofstream fout;
	int n;
	
	fin>>n;

	if((n<1)||(n>100))
	{
		cout<<"Error!n must be in [1,100]";
		exit(0);
	}
	int * y=new int[n];
	
	int s;

    int row;//每次处理的行数（可变）

    int num=0;

    int j;
	
	for(int i=0;i<n;i++)
		num+=i+1;//num是数字的总个数;

    int * x=new int[num];

//

    for(i=0;i<n;i++)
		y[i]=0;

//

	for(i=0;i<num;i++)
		fin>>x[i];
	fout.open("output.txt");
	
	for(row=n;row>=1;row--)
	{
		s=(row*(row-1))/2;//s是由行数换算成的该行首个元素对应数组中的位置
		for(j=0,i=row;i>=1;i--)
		{
			x[s+j]+=y[j];
			j++;
		}
		
		for(j=0,i=row;i>1;i--)
		{
			if(x[s+j]>x[s+j+1])
				y[j]=x[s+j];
			
			else 
				y[j]=x[s+j+1];
			j++;
		}
		
		fout<<"("<<row<<","<<j<<")"<<endl;

	}


    fout<<x[0]<<endl;

    fin.close();

    fout.close();

}