首页 > ACM题库 > HDU-杭电 > hdu 2287 Ghosts In The Robots待解决[解题报告]C++
2014
01-05

hdu 2287 Ghosts In The Robots待解决[解题报告]C++

Ghosts In The Robots

问题描述 :


Do you still remember the movie "I, robot" ? In that movie, Sunny is a very special, unique robot who can dream! As we known, robot is a machine installed with artificial intelligence, and it can’t response to the situations which are not contained in the pre-designed programs. But the creator of Sunny detects that the logic sequences existed in the robot would change under some particular cases, e.g. magnetic field, noises etc. He called this unpredictable sequence ghosts in the robot because these random combination of 1s and 0 s could yield unpredictable behaviors of robots, it was terrible! In order to detect this situation as soon as possible, you should help the prof. via your outstanding programming skills.
You would be given a sequence with the length of N, and this sequence is only contained 0 and 1.Based on the professor’s recent research data, the sequence could have at most F successive bits flipped(that means 0 changes to 1, and 1 changes to 0) and could have at most R successive bits remained the same. Based on these situations, you should calculate the maximum number of 1 in the sequence after those changes.

输入:

The input would have multiple test cases, each test case has two lines, The first line contains two integer R and F(1 <= R <= 50, 1 <= F <= 50), indicating the number of the digits remain the same and the number of the digits flipped respectively. the second line is a sequence only comprises of 0 and 1, whose length is between 1 and 1000.The input would end when R == 0 and F == 0.

输出:

The input would have multiple test cases, each test case has two lines, The first line contains two integer R and F(1 <= R <= 50, 1 <= F <= 50), indicating the number of the digits remain the same and the number of the digits flipped respectively. the second line is a sequence only comprises of 0 and 1, whose length is between 1 and 1000.The input would end when R == 0 and F == 0.

样例输入:

4 1
1111
2 2
1111
0 0

样例输出:

4
3


Hint
Hint For test case 2, one change is like this: 1 1 1 1 Remain Flip Remain Remain So the answer is 3


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  5. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!