Luogu P1118 Digital Triangle

Luogu P1118 Digital Triangle

Topic link:  www.luogu.com.cn/problem/P11...


The general idea is DFS, but you need to pay attention to pruning, otherwise it will time out.

After writing a, ab, abc, and abcd by hand, I found that the coefficients of the sum of the inverted triangles are regular. After reading the solution, I remembered that it was the nth row of Yang Hui's triangle, so you can first hit the nth row of Yang Hui's triangle The table is typed out, and then DFS judges whether the current result has exceeded sum every time it enters one layer, and it returns directly if it exceeds.

The m-th number in the n-th row of Yanghui's triangle =  C(n-1, m-1), which can be calculated according to the combination number formula. This question n is not too big and can be calculated hard. However, after reading the solution, you can calculate it like this: C(n,r) = [(n-r+1)/r] * C(n, r-1); You can deduce the details yourself. In this way, the next number can be derived from the previous number. The starting boundary is 1, and the Yang Hui triangle is symmetrical.


AC code:

#include<iostream>
using namespace std;

int n, sum;
int a[15];
int yanghui[15];
int vis[15];
void dfs(int cur);
int judge(int cnt);
bool flag = false;

int main(void)
{
    cin >> n >> sum;
    
    //n 
    yanghui[1] = yanghui[n] = 1;
    for(int i = 2; i <= n/2; i++)
        yanghui[i] = yanghui[n+1-i] = (n-i+1) * yanghui[i-1]/(i-1);
    if(n & 1 && n != 1)
        yanghui[n/2+1] = (n/2+1) * yanghui[n/2]/(n/2);

    dfs(1);
    return 0;
}

void dfs(int cur)
{

    if(cur == n+1){
        if(judge(n) == sum){
            for(int i = 1; i < n; i++)
                cout << a[i] << " ";
            cout << a[n] << endl;

            flag = true;
            return;
        }
    }

    if(flag)
        return;
    if(judge(cur-1) > sum) 
        return;

    for(int i = 1; i <= n; i++)
    {
        if(flag)
            return;
        
        if(vis[i])  
            continue;

        a[cur] = i;
        vis[i] = 1;
        dfs(cur+1);
        vis[i] = 0;
    }
}

int judge(int cnt)
{
    int res = 0;
    for(int i = 1; i <= cnt; i++)
        res += yanghui[i] * a[i];
    return res;
}