T3-4
2024-10-02 16:00:05
发布于:天津
30%
1、 求全排列,可以使用线性dp取求解从上往下最后一行第一个数的数值,等于sum即可输出
$O(n!* n^2) $
#include<bits/stdc++.h>
using namespace std;
int f[15][15] ;
int n,a[15],sum;
int main()
{
cin >> n >> sum ;
for(int i = 1 ; i <= n ; i ++ )a[i] = i ;
do{
for(int i = 1 ; i <= n ; i ++ ) f[1][i] = a[i];
for(int i = 2 ; i <= n ; i ++ ){
for(int j = 1 ; j <= n - i + 1 ; j ++ )
{
// 推出f[n][1]
f[i][j] = f[i-1][j] + f[i-j][j+1];
}
}
if(sum == f[n][1])
{
for(int i = 1 ; i <= n ; i ++ ){
cout << a[i] << " " ;
}
}
cout << endl;
return 0;
}while(next_permutation(a+1,a+1+n)) ;
return 0;
}
对于60%的数据
考虑到对于每一个排列,每一个数字a[i]能够提供的价值为多少
例如n = 5 的时候,假设当前排列为变量abcdef,那么我们可以尝试去计算每一个数的贡献次数为多少。
a b c d e
a+b b+c c+d d+e
a+2b+c b+2c+d c+2d+E
.....
a+4b+6c+4d+e
大概每个数字上14641次贡献。
每个数字能够产生的贡献次数的系数,约等于杨辉三角的第n航的系数,我们可以预处理出杨辉三角每一行的对应系数,在枚举全排列时就可以套用对应系数直接带入处理,计算优化为O(n!) -> O(n) 。勉强通过
预处理代码
c[1][1] = 1;
for(int i = 2 ; i <= n ; i ++ ){
for(int j = 1 ; j <= i j ++ )
{
c[i][j] = c[i-1][j] + c[i-1][j-1] ;
}
}
替换掉动态规划即可
100%
在计算的时候,一边枚举全排列,一遍进行计算杨辉三角系数贡献,若总贡献超出sum,那么当前排列直接不在计算,断掉,通过这样的方式来做一个剪枝
这里空空如也
有帮助,赞一个