题解 洛谷P1118 数字三角形

发布于 2019-06-23  16 次阅读


题目地址

首先先认真地读完这道题,可以发现几个条件:

  • 要求输出的是1至n的排列,即输出序列包含1至n的所有整数 (我都不好意思说我死在这里)

  • 每次将相邻两个数相加,构成新的序列,序列长度-1

  • 给定sum要求倒着做

接着发现题目序列操作的规律

大家可以自己先在草稿纸上写一下,假设第一行的n个数分别为a,b,c,...

如果n为4,那么sum是a+3b+3c+d。

如果n为5,那么sum是a+4b+6c+4d+e。

如果n为6,那么sum是a+5b+10c+10d+5e+f。

观察各项的系数,你发现了什么?

根据多年做小学奥数类编程题的经验,这是一个杨辉三角形

预处理完杨辉三角形,由于题目要求是按照大小排列,所以用dfs无疑是最好的解决方法,可以在搜索的时候保证找到的序列始终是最小的一组。所以只要找到合法的一组a,b,c,...,就可以得出答案了

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 110

using namespace std;

int n,maxn;
bool vis[N];
int ans[N],yh[N][N],a[N];//yh[]存杨辉三角 a[]存最后一行 

bool dfs(int x,int num,int val) 
//i表示正在搜索第i个数(从1开始),num表示第i个数是num,v表示前i个数的杨辉三角和为v
{
    if (val>maxn) return false;
    if (x==n)
        if (val==maxn)
		{
            ans[x]=num;
            return true;
        }
        else return false;
    vis[num]=true;
    for (int i=1;i<=n;i++) //为1至n的排列
	{
        if ( (vis[i]==false) && (dfs(x+1,i,val+a[x+1]*i)==true) )
		{
            ans[x]=num;
            return true;
        }
    }
    vis[num]=false;//毁尸灭迹 
    return false;
}

int main()
{
	memset(yh,0,sizeof(yh));
    cin>>n>>maxn;
    yh[1][1]=1;
    for (int i=2;i<=n;i++)
    	for (int j=1;j<=i;j++)
    		yh[i][j]=yh[i-1][j]+yh[i-1][j-1];
    for (int i=1;i<=n;i++)
    	a[i]=yh[n][i];
    if (dfs(0,0,0))
        for (int i=1;i<=n;i++)
            cout<<ans[i]<<' ';
	cout<<endl; 
    return 0;
}

Cause this is the life. Living is do or die.