题号：P1118
必须用杨辉三角/组合数的方法做，同时要剪枝……这样才能A。不用这个只能60，剩下的全部TLE。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int n,sum; bool check[13]; int current[13]; int current_temp[13]; int yanghui[13]; int calculate(int k){ int sum=0; for(int i=0;i<k;i++){ sum+=yanghui[i]*current[i]; } return sum; } void search(int level){ if(level==n&&calculate(n)==sum){ for(int i=0;i<n;i++){ cout<<current[i]<<" "; } exit(0); } for(int i=1;i<=n;i++){ if(!check[i]){ check[i]=true; current[level]=i; if(calculate(level)<sum)search(level+1); check[i]=false; } } } int main(){ memset(check,false,sizeof(check)); cin>>n>>sum; //calculate yanghui yanghui[0]=1; for(int i=1;i<n;i++){ yanghui[i]=(n-i)*yanghui[i-1]/i; } //end calculate search(0); } |
20180730更新：都忘了杨辉三角了……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include<iostream> using namespace std; int n,sum; bool visited[15]; int ansarr[15]; int triangle[15][15]; void triangle_init(){ for(int i=0;i<15;i++){ triangle[i][0]=1; triangle[i][i]=1; } for(int i=2;i<15;i++){ for(int j=1;j<i;j++){ triangle[i][j]=triangle[i-1][j]+triangle[i-1][j-1]; } } } bool dfs(int pos,int s){ if(pos==n+1)return s==sum; if(s>sum)return false; for(int i=1;i<=n;i++){ if(visited[i])continue; visited[i]=true; ansarr[pos]=i; if(dfs(pos+1,s+i*triangle[n-1][pos-1]))return true; visited[i]=false; } return false; } int main() { triangle_init(); cin>>n>>sum; if(dfs(1,0))for(int i=1;i<=n;i++)cout<<ansarr[i]<<" "; } |