读题点 这里

题意简述

给定一个金字塔(第 ii 层有 ii 个房间),设第 ii 层的第 jj 个房间为 ai,ja_{i,j} ,那么可以从 ai,ja_{i,j} 到达 ai+1,ja_{i+1,j}ai+1,j+1a_{i+1,j+1}。每个房间可以选择放 11 个灯泡或者不放,每个房间的亮度是所有能到达这个房间并且放了灯泡的房间的数量,要求第 ii 行的 ii 个房间亮度相同,请求出一种放灯泡的方案使放置的灯泡数量最多。

思路分析

我们只要在每一行两端的房间中放置灯泡,就可以使第 ii 行的 ii 个房间亮度相同。

例如,当 i=5i=5 时,灯泡的摆放为

1
2
3
4
5
1
1 1
1 0 1
1 0 0 1
1 0 0 0 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int T,n;

int main(){
cin>>T;
while(T--){
cin>>n;
cout<<1<<endl;
for(int i=2;i<=n;i++){
cout<<1<<" ";
for(int j=2;j<=i-1;j++) cout<<0<<" ";
cout<<1<<endl;
}
}
//system("pause");
return 0;
}