最近485批了挺快啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

最近485批了挺快啊

最近485批了挺快啊# Immigration - 落地生根

b*g2011-01-15 08:01

1 楼

网上看到的，不会做：
一条直线上有40个电线杆，每个间隔5米。现在要把9个灯泡拧上去，每个
电线杆上至多一个，而且不能有三个这样的灯泡，比如说A, B, C,
AB间的距离等于BC间的距离。问这9个灯泡有多少种放法？
谢谢

y*e2011-01-15 08:01

2 楼

一连三个case都是一个月或者多点

b*g2011-01-15 08:01

3 楼

up

【在 b*******g 的大作中提到】

: 网上看到的，不会做：
: 一条直线上有40个电线杆，每个间隔5米。现在要把9个灯泡拧上去，每个
: 电线杆上至多一个，而且不能有三个这样的灯泡，比如说A, B, C,
: AB间的距离等于BC间的距离。问这9个灯泡有多少种放法？
: 谢谢

d*l2011-01-15 08:01

4 楼

你也快了，我的FP都还没收到呢一个多月了

d*l2011-01-15 08:01

5 楼

只能想到搜索的办法，好像找不到什么递推或者是能简化问题的规律

y*e2011-01-15 08:01

6 楼

快了快了，你肯定快了

你也快了，我的FP都还没收到呢一个多月了

【在 d**l 的大作中提到】

: 你也快了，我的FP都还没收到呢一个多月了

d*d2011-01-15 08:01

7 楼

n*y2011-01-15 08:01

8 楼

A,B,C 是连续的3根电线杆的话，还是很好写代码算出来的。。
就是不知道是不是任意的3根电线杆。。

b*g2011-01-15 08:01

9 楼

是任意的...

【在 n********y 的大作中提到】

: A,B,C 是连续的3根电线杆的话，还是很好写代码算出来的。。
: 就是不知道是不是任意的3根电线杆。。

n*y2011-01-15 08:01

10 楼

IDEA:
int place(possible_positions, need_to_place, current_interval, distances[])
place(A,B,C,D) = place (A-1, B, C+1, D) +
place(A-1, B-1,0, D') / place(A-2, B, C+2,D)
if c+1 not in D[] if c+1 in D[]
add c+1 to end of D[]

d*l2011-01-15 08:01

11 楼

搜索出来是5231490种方法，不知有没有别的方法

【在 b*******g 的大作中提到】

: 是任意的...

b*g2011-01-15 08:01

12 楼

怎么搜出来的5231490?

【在 d*******l 的大作中提到】

: 搜索出来是5231490种方法，不知有没有别的方法

d*l2011-01-15 08:01

13 楼

#include
using namespace std;
int f[110];
int p[50];
int cur = 1;
int ans;
void solve(int n, int m, int s)
{
if(m == 0) {
/* for(int i = 0; i < cur; i++)
cout << p[i]+1 << " ";
cout << endl;
*/ ans += n-1-p[cur-1];
return ;
}
for(int i = s; i < n; i++) {
if(!f[i]) {
p[cur++] = i;
for(int j = cur-1; j >= 0; j--)
if(2*i-p[j] < n)
f[2*i-p[j]]++;
solve(n, m-1, i+1);
for(int j = cur-1; j >= 0; j--)
if(2*i-p[j] < n)
f[2*i-p[j]]--;
cur--;
}
}
}
int main()
{
solve(40, 8, 1);
cout << ans << endl;
return 0;
}

【在 b*******g 的大作中提到】

: 怎么搜出来的5231490?