USACO06FEB数字三角形|题解

---

1

观察易得 答案实际上是一个杨辉三角形分别乘上对应数字的和

杨辉三角形

直接打表即可

    int yanghui[13][13] = {{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,0,0,0,0,0,0,0,0,0},
{0,1,2,1,0,0,0,0,0,0,0,0,0},
{0,1,3,3,1,0,0,0,0,0,0,0,0},
{0,1,4,6,4,1,0,0,0,0,0,0,0},
{0,1,5,10,10,5,1,0,0,0,0,0,0},
{0,1,6,15,20,15,6,1,0,0,0,0,0},
{0,1,7,21,35,35,21,7,1,0,0,0,0},
{0,1,8,28,56,70,56,28,8,1,0,0,0},
{0,1,9,36,84,126,126,84,36,9,1,0,0},
{0,1,10,45,120,210,252,210,120,45,10,1,0},
{0,1,11,55,165,330,462,462,330,165,55,11,1}
};

生成杨辉的代码

for (int i = 1;i <= 12;++ i){
        yanghui[i][1] = yanghui[i][i] = 1;
        for (int j = 2;j < i;++ j){
            yanghui[i][j] = yanghui[i - 1][j - 1]+yanghui[i - 1][j];
        }
    }printf("{");
    for (int i = 0;i <= 12;++ i){
        printf("{");
        for (int j = 0;j <= 11;++ j)
            printf("%d,",yanghui[i][j]);
        printf("%d},\n",yanghui[i][12]);
    }
    printf("}\n");

---

2

然后这道题就成了求1-n的全排列
这里我用了swap实现全排列

void dfs(int handle,int weight){
    for (int i = handle;i <= n;++ i){
        swap(arr[i],arr[handle]);
        dfs(handle + 1,weight + arr[handle] * yanghui[n][handle]);
        swap(arr[i],arr[handle]);
    }
    return ;
}

---

3

但这样不保证字典序
通过观察可以发现 杨辉三角满足轴对称
例如n = 4 时a b c d和a c b d和d b c a和d c b a这样不同的排序可以得到相同的sum
因此我在输出时强行把它变成字典序

if (handle > n && weight == m){
        for (int i = 1;i <= n;++ i)
        {
            if (i <= n / 2 && arr[n - i + 1] < arr[i])
                swap(arr[i],arr[n - i + 1]);
            printf("%d ",arr[i]);
        }
        exit(0);
    }

这个方法不确保答案的正确性 但在n<=12的规模下还是不会出问题的

---

4

最后加上一行剪枝if (weight >= m) return;