b*******g
发帖数: 66 | 1 网上看到的，不会做：
一条直线上有40个电线杆，每个间隔5米。现在要把9个灯泡拧上去，每个
电线杆上至多一个，而且不能有三个这样的灯泡，比如说A, B, C,
AB间的距离等于BC间的距离。问这9个灯泡有多少种放法？
谢谢 | b*******g
发帖数: 66 | 2 up
【在 b*******g 的大作中提到】
: 网上看到的，不会做：
: 一条直线上有40个电线杆，每个间隔5米。现在要把9个灯泡拧上去，每个
: 电线杆上至多一个，而且不能有三个这样的灯泡，比如说A, B, C,
: AB间的距离等于BC间的距离。问这9个灯泡有多少种放法？
: 谢谢
| d*******l
发帖数: 338 | 3 只能想到搜索的办法，好像找不到什么递推或者是能简化问题的规律 | d*******d
发帖数: 2050 | | n********y
发帖数: 66 | 5 A,B,C 是连续的3根电线杆的话，还是很好写代码算出来的。。
就是不知道是不是任意的3根电线杆。。 | b*******g
发帖数: 66 | 6 是任意的...
【在 n********y 的大作中提到】
: A,B,C 是连续的3根电线杆的话，还是很好写代码算出来的。。
: 就是不知道是不是任意的3根电线杆。。
| n********y
发帖数: 66 | 7 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*******l
发帖数: 338 | 8 搜索出来是5231490种方法，不知有没有别的方法
【在 b*******g 的大作中提到】
: 是任意的...
| b*******g
发帖数: 66 | 9 怎么搜出来的5231490?
【在 d*******l 的大作中提到】
: 搜索出来是5231490种方法，不知有没有别的方法
| d*******l
发帖数: 338 | 10 #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?
|
|
