有2个题目,被卡住了
第一个题目是,给定n个区间，然后找出所有区间里可以整个覆盖其他区间的最大覆盖量，比如：
1 3
2 5
5 8
3 6
2 5
3 8
3 6
3 8
就输出最大4， 因为对应每个输入的区间可以覆盖其他区间的数量就是0, 1, 0, 1, 1, 4, 1, 4
第一个1-3没办法覆盖任何其他，而第二个2-5可以覆盖另外一个2-5，所以是2，
而最后一个可以覆盖另外的3-8,3-6,3-6,5-8,所以就是4
第二题是给定一个一维的棋盘，刚开始棋盘式满的，目的是清空整个棋盘
规则如下：
-在任何情况下都可以去除或者填充第一个格子。
-如果第一个格子是满的那么我们就可以去除或者填满第二个格子(对N>=2也适用)
-若要去除或者填充第3<=K<=N的格子，只有在第K-1个格子是满的并且所有第1到第K-2个格子是空的时候才可以。
给个操作图，刚开始时4个格子
[解决办法]
第一小题:
1. 设置数组 Cnt[n] 存储各个区间能覆盖其它区间的个数,初值为 0;
2. for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (i!=j && 第 i 个区间能覆盖第 j 个区间) Cnt[i]++;
3. 在 Cnt[..] 中寻找最大者
上面算法耗时 O(n*n)
第二小题:
对于当前棋盘,实际上有两个后继状态:1) 首个方格状态取反(若有子,则删除,若无子,则填子) 2) 首个有子的右侧状态取反(若有子,则删除,若无子,则填子).算法如下:
1. 定义集合S,它的初值为 S={<1,....1>};
2. for (i=1;i<=
[解决办法]
S
[解决办法]
;i++)
3. {
4. 令 P=S[i];
5. Q=P;
6. if (P[0]==1) // 若有子
7. {
8. p[0]=0; // 删除该棋子
9. if (P[0..n-1]全为 0) return 完成; // 可用增加链指针,输出删子步骤
10. }
11. else // 若无子
12. {
13. P[0]=1; // 落子
14. }
15. if (P 不在 S 中) S=S+{P};
16. 在 Q[0..n-1] 中查找首个为 1 的下标,令它是 i;
17. if (i<n-1)
18. {
19. Q[i+1]=1-Q[i+1]; // 右侧状态取反
20. if (Q 不在 S 中) S=S+{Q};
21. }
22. }
23. 返回:无解
算法耗时 O(2^n)
[解决办法]
第一个题目简单，依次遍历
第二个题目，用递归，这个算法有点像汉诺塔和九连环
