求一分治算法的问题的解法
本帖最后由 rockerz 于 2014-4-28 22:31 编辑输入为N和C。你要把N个连续自然数任意排列。如果i在j前面，并且i>j,积分+1。问题要求积分必须等于C。输出有多少种排列方法。 0<=N<=10000<=C<=10,000
示例： １４３２ 积分为3， 因为 (４，３)，（４，２），（３，２）。
示例输入1
10 1
示例输出1
9
示例输入2
4 3
示例输出2
6
我已经写了一个暴力的算法，但是暴力终究不是解决问题的办法。。N超过50时就有64位数不同的排列方法了。。然后再一一查看是否符合C，电脑肯定卡爆。
声明：这道题不是作业，不是考试题。是我出于爱好去尝试的。本人已经自己网上找过，但无法找到解题思路。
附上我的暴力解法。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int a;
int n,c,count=0,solc=0;;
scanf("%d %d",&n,&c);
for (int i=0;i<n;i++){
a=i;
}
do {
count=0;
for (int i=0;i<n;i++){
for (int j=i;j<n;j++){
if (a>a)count++;
}
if (count>c)break;
}
if (count==c)solc++;
} while (next_permutation(a,a+n));
printf("%d",solc);
return 0;
}
自己顶一下
页:
[1]