首页 > 代码库 > POJ 3187 Backward Digit Sums
POJ 3187 Backward Digit Sums
http://poj.org/problem?id=3187
穷竭搜索 全排列 然后按规则求和 排列之前先按升序排序
这样可以保证第一个和为k的就是符合最小序列的结果
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 int sum(int a[], int n) 8 { 9 int s[11]; 10 for (int i = 0; i < n; i++) 11 { 12 s[i] = a[i]; 13 } 14 while (n != 1) 15 { 16 n--; 17 for (int i = 0; i < n; i++) 18 { 19 s[i] += s[i+1]; 20 } 21 } 22 return s[0]; 23 } 24 int main() 25 { 26 int s,n; 27 int a[11], calc[11]; 28 freopen("in.txt","r", stdin); 29 while (~scanf("%d%d", &n, &s)) 30 { 31 for(int i = 0; i < n; i++) 32 { 33 a[i] = i+1; 34 } 35 do 36 { 37 for (int i =0 ;i < n; i++) 38 { 39 calc[i] = a[i]; 40 } 41 if ( sum(calc, n) == s) break; 42 }while (next_permutation(a, a+n)); 43 for (int i =0 ; i < n; i++) 44 { 45 printf("%d ", calc[i]); 46 } 47 putchar(‘\n‘); 48 } 49 return 0; 50 }
POJ 3187 Backward Digit Sums
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。