鱼C论坛

 找回密码
 立即注册
查看: 2674|回复: 1

求一分治算法的问题的解法

[复制链接]
发表于 2014-4-27 10:48:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 rockerz 于 2014-4-28 22:31 编辑

输入为N和C。你要把N个连续自然数任意排列。如果i在j前面,并且i>j,积分+1。问题要求积分必须等于C。输出有多少种排列方法。 0<=N<=1000  0<=C<=10,000

示例: 1432 积分为3, 因为 (4,3),(4,2),(3,2)。

示例输入1
10 1
示例输出1
9

示例输入2
4 3
示例输出2
6

我已经写了一个暴力的算法,但是暴力终究不是解决问题的办法。。N超过50时就有64位数不同的排列方法了。。然后再一一查看是否符合C,电脑肯定卡爆。
声明:这道题不是作业,不是考试题。是我出于爱好去尝试的。本人已经自己网上找过,但无法找到解题思路。

附上我的暴力解法。
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;

  5. int main()
  6. {
  7.         int a[50];
  8.         int n,c,count=0,solc=0;;
  9.         scanf("%d %d",&n,&c);
  10.         for (int i=0;i<n;i++){
  11.                 a[i]=i;
  12.         }
  13.         do {
  14.                 count=0;
  15.                 for (int i=0;i<n;i++){
  16.                         for (int j=i;j<n;j++){
  17.                                 if (a[i]>a[j])count++;
  18.                         }
  19.                         if (count>c)break;
  20.                 }
  21.                 if (count==c)solc++;
  22.         } while (next_permutation(a,a+n));
  23.         
  24.         printf("%d",solc);
  25.         return 0;
  26. }
复制代码


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2014-4-28 22:29:49 | 显示全部楼层
自己顶一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 09:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表