b*******g 发帖数: 66 | 1 网上看到的,不会做:
一条直线上有40个电线杆,每个间隔5米。现在要把9个灯泡拧上去,每个
电线杆上至多一个,而且不能有三个这样的灯泡,比如说A, B, C,
AB间的距离等于BC间的距离。问这9个灯泡有多少种放法?
谢谢 | b*******g 发帖数: 66 | 2 up
【在 b*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 网上看到的,不会做: : 一条直线上有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是任意的...
| b*******g 发帖数: 66 | 9 怎么搜出来的5231490?
【在 d*******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 搜索出来是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么搜出来的5231490?
|
|