OJ Board

Code: Select all

#include <stdio.h>
#include <math.h>
#include <memory.h>
#define MIN(a,b) (a)<(b)?(a):(b)
int num[70][70];
bool visited[70][70];
int main()
{
	int m,i,j;
	while(true){
		memset(num,1<<30,sizeof(num));
		memset(visited,false,sizeof(visited));
		scanf("%d",&m);
		if(!m) break;
		int mag=0;
		bool flag=true;
		for(i=(2*m-1);i>0;i--){
			if(mag<m&&flag) mag=mag+1;
			else{flag=false;mag--;}
			for(j=1;j<=mag;j++){
				scanf("%d",&num[i][j]);
				visited[i][j]=true;
			}
		}
		//dp
		for(i=1;i<(2*m-1);i++){
			for(j=1;j<=i;j++){
					if(num[i+1][j]&&visited[i+1][j]==true&&num[i][j])
					{
						num[i+1][j]=MIN(abs(num[i][j]+num[i+1][j]),abs(num[i][j]-num[i+1][j]));
						visited[i+1][j]=false;
					}
					if(visited[i+1][j+1]==true&&num[i][j+1]&&num[i][j]&&num[i+1][j+1])
					{
						int temp1=MIN(abs(num[i][j]+num[i+1][j+1]),abs(num[i][j]-num[i+1][j+1]));
						int temp2=MIN(abs(num[i][j+1]+num[i+1][j+1]),abs(num[i][j+1]-num[i+1][j+1]));
						if(temp1<temp2)
						{
							num[i+1][j+1]=temp1;
							visited[i+1][j+1]=false;
						}
						else
						{
							num[i+1][j+1]=temp2;
							visited[i+1][j+1]=false;
						}
					}
			}
		}
		//
		printf("%d\n",num[2*m-1][1]);
	}
	return 0;
}