OJ Board

Code: Select all

#include<iostream>
#define MAX 12

using namespace std;
int s[MAX][MAX];

void print(int i,int j)
{
	if(i==j)
		cout<<"A"<<i;
	else
	{
		cout<<"(";
		print(i,s[i][j]);
		cout<<" x ";
		print(s[i][j]+1,j);
		cout<<")";
	}
}

int main()
{
	int N,i,j,p[11],t,l,k,c=0;
	unsigned long m[MAX][MAX];


	while(cin>>N)
	{
		if(N==0) break;
		
		c++;
		for(i=0,j=0;i<N*2-1;i++)
		{
			cin>>t;
			if(i%2 == 0)p[j++]=t;
		}
		cin>>p[j];

		for(i=1;i<=N;i++) m[i][i]=0;
		for(l=2;l<=N;l++)
		{
			for(i=1;i<=N-l+1;i++)
			{
				j=i+l-1;
				m[i][j]=4294967295;
;
			
				for(k=i;k<=j-1;k++)
				{
					t=m[i][k] + m[k+1][j] + p[i]*p[k]*p[j];									
					if(t<m[i][j])
					{
						m[i][j]=t;
						s[i][j]=k;
					}
				}
			}
		}
	
		cout<<"Case "<<c<<": ";
		print(1,N);
		cout<<"\n";
	
	}

	return 0;
}

Code: Select all

#include<iostream>
#include<vector>
using namespace std;
#define max 1E7

void prin(int s[1000][1000],int i, int j)
{
  if(i==j)
    cout<<"A"<<i;
  else
    {
      cout<<"(";
      prin(s,i,s[i][j]);
      cout<<" x ";
      prin(s,s[i][j]+1,j);
      cout<<")";
    }
}
main()
{
  int N;
  int cases=1;
  while(cin>>N)
    {
      if(N==0)
	break;
      cout<<"Case "<<cases<<": ";
      cases++;
      int cost[1000][1000]={max};
      int s[1000][1000];
      
      vector<int> p;
      int temp;
      for(int i=0;i<N;i++)
	{
	  cin>>temp;
	  p.push_back(temp);
	  cin>>temp;
	}
      p.push_back(temp);
      int n=p.size()-1;
      for(int i=1;i<=n;i++)
	{
	  cost[i][i]=0;
	}
      for(int l=2;l<=n;l++)
	{

	  for(int i=1;i<=n-l+1;i++)
	    {
	      int j=i+l-1;
	      cost[i][j]=max;
	      for(int k=i;k<=j-1;k++)
		{
		  int q=cost[i][k]+cost[k+1][j]+p[i-1]*p[k]*p[j];
		  if(q<cost[i][j])
		    {
		      cost[i][j]=q;
		      s[i][j]=k;
		    }
		}
	    }
	}

      prin(s,1,N);
      cout<<'\n';

    }
}

Code: Select all

int main() {... return 0; }

Code: Select all

#include <stdio.h>
#include <string.h>

int n;
int idx;
int row[10], col[10];
int map[100][100];
int que[100][100];

int init()
{   memset(map, 0, sizeof(map));
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));

    return 0;
    }

int cal()
{   int j, tmp;

    for (int i = 0; i < n; i++)
    {	map[i][i] = 0;
	    }
    for (int l = 1; l < n; l++)
    {	for (int i = 0; i < n - l; i++)
	    {	j = i + l;
	        printf("%d %d\n", i, j);
		    map[i][j] = 32767;
		    for (int k = i; k < j; k++)
		    {	tmp = map[i][k] + map[k + 1][j] + row[i] * col[k] * col[j];
			    if (tmp < map[i][j])
			    {  map[i][j] = tmp;
				   que[i][j] = k;
				   }
                }
            }
        }    
    return 0;
    }

int outpt(int arg[][100], int i, int j)
{   if (i == j)
    {  printf("A%d", i + 1);
       }
    else
    {   printf("(");
        outpt(arg, i, arg[i][j]);
        printf(" x ");
        outpt(arg, arg[i][j] + 1, j);
        printf(")");
        }
    return 0;
    }

int inpt()
{
    idx = 0;
    
    do
    { init();
      scanf("%d", &n);
      if (n != 0)
      {  idx++;
         //printf("Case %d: ", idx);
         for (int i = 0; i < n; i++)
         {   scanf("%d %d", &row[i], &col[i]);
             }
         cal();
         //outpt(que, 0, n - 1);
         printf("\n");
         }
      } while (n != 0);
    return 0;
    }

int main()
{   
    inpt();
    return 0;
    }