首页 > ACM题库 > HDU-杭电 > HDU 3805-Triangle Conjecture[解题报告]HOJ
2015
04-13

HDU 3805-Triangle Conjecture[解题报告]HOJ

Triangle Conjecture

问题描述 :

One could construct a triangle with the digit 1 to 9 as the figure below:
Query on a tree
The triangle is the one that the sums of every four numbers on its three edges are all equals to 23. Moreover, 23 is the biggest summation one can get from this kind of arraignment of digits. Your task is even tougher, given a positive integer n, you should use integer from 1 to 3*(n-1) to construct triangle with equal summation of digits on the three edges and the summation is the biggest among all the possible arraignments. For example, if n = 4, then you should choose number from 1 to 3*(4-1).
For convenience, the output format for a certain triangle is like the example for the figured triangle above:
95 41 38 2 6 7
The numbers are separated by a single space in each row, and there are no spaces at the end of each row.
Note that there may be several solutions exist, arbitrary one of them will be accepted.

输入:

The first line of the input contains a number t indicates the number of test cases.  Following t lines, each line will contains only one integer n denoting the side length of the desired triangle. ( t≤20, 3≤n≤1000)

输出:

The first line of the input contains a number t indicates the number of test cases.  Following t lines, each line will contains only one integer n denoting the side length of the desired triangle. ( t≤20, 3≤n≤1000)

样例输入:

2
3
4

样例输出:

6
1 2
5 3 4
9
5 4
1 3
8 2 6 7

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

struct nod
{
	int flag,sum,a[10005];
}node[3];

void setflag()
{
	if(node[0].sum<node[1].sum && node[0].sum<node[2].sum)node[0].flag=1;
	if((node[0].sum<node[1].sum && node[0].sum>node[2].sum) || (node[0].sum>node[1].sum && node[0].sum<node[2].sum))node[0].flag=2;
	if(node[0].sum>node[1].sum && node[0].sum>node[2].sum)node[0].flag=3;
	if(node[1].sum<node[0].sum && node[1].sum<node[2].sum)node[1].flag=1;
	if((node[1].sum<node[2].sum && node[1].sum>node[0].sum) || (node[1].sum>node[2].sum && node[1].sum<node[0].sum))node[1].flag=2;
	if(node[1].sum>node[0].sum && node[1].sum>node[2].sum)node[1].flag=3;
	if(node[2].sum<node[1].sum && node[2].sum<node[0].sum)node[2].flag=1;
	if((node[2].sum<node[1].sum && node[2].sum>node[0].sum) || (node[2].sum>node[1].sum && node[2].sum<node[0].sum))node[2].flag=2;
	if(node[2].sum>node[1].sum && node[2].sum>node[0].sum)node[2].flag=3;
}

int main()
{
	int i,j,t,n,cnt[3];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(node,0,sizeof(node));
		for(j=0;j<3;j++)
		{
			node[j].flag=j+1;
			node[j].sum=j+1;
			node[j].a[0]=j+1;
		}
		for(i=1;i<n-2;i++)
		{
			setflag();
			for(j=0;j<3;j++)
			{
				if(node[j].flag==1)
				{
					node[j].a[i]=3*i+2;
					node[j].sum+=(3*i+2);
				}
				if(node[j].flag==2)
				{
					node[j].a[i]=3*i+3;
					node[j].sum+=(3*i+3);
				}
				if(node[j].flag==3)
				{
					node[j].a[i]=3*i+1;
					node[j].sum+=(3*i+1);
				}
			}
		}
		setflag();
		for(i=0;i<3;i++)
		{
			if(node[i].flag==1)cnt[0]=i;
			if(node[i].flag==2)cnt[1]=i;
			if(node[i].flag==3)cnt[2]=i;
		}
		printf("%d\n",3*n-3);
		for(i=0;i<n-2;i++)printf("%d %d\n",node[cnt[0]].a[i],node[cnt[1]].a[i]);
		printf("%d ",3*n-4);
		for(i=0;i<n-2;i++)printf("%d ",node[cnt[2]].a[i]);
		printf("%d\n",3*n-5);
	}

	return 0;
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。