Bloomberg : 输出排列个数

//Write an algorithm to find the number
//of six digit numbers where the sum of the first three digits is equal to the sum of the last three digits.

其实就是求three digits加起来等于k的排列有几种

回复 2# Etrnls
有道理！这样可以先预处理一下，3重循环算出3个数的和的组成方式的数目，要注意避免重复。然后就可以过一遍所有可能的和并且算出答案

第一个数字如果不能是0还麻烦点，需要单独考虑下

1.         int way3[30], way2[30];
   
2.         int ans = 0;
   
3.         int i, j, k;
   
4.         memset(way3, 0, sizeof(way3));
   
5.         memset(way2, 0, sizeof(way2));
   
6.         for(i = 0; i < 10; i++) for(j = 0; j < 10; j++) {
   
7.                 for(k = 0; k < 10; k++)
   
8.                         way3[i+j+k]++;
   
9.                 way2[i+j]++;
   
10.         }
    
11.         for(i = 0; i < 30; i++)
    
12.                 ans += (way3[i]-way2[i])*way3[i];
    
13.         cout << ans << endl;

复制代码

是dp吗?开一个table[3][sum]. 复杂度为3sum

是dp吗?开一个table[3][sum]. 复杂度为3sum
bill 发表于 2011-5-15 01:12

类似DP,但你的做法好像不对

darksteel 发表于 2011-5-12 00:15

    不错哦