(4)  接上一篇 水题..(1) 中的第2题,其实我一早就怀疑念珠这道题是有O(n)的解法的,可惜因为题目的数据规模比较小,我直接暴力过了..今天好无聊,于是重新看了遍题目,很神奇的看出了动态规划的转移方程.想法是这样子的: 分别用数组left_r,left_b,right_r,right_b表示在项链i处向左,右能够收集到的篮色`红色珠子数..因为念珠是环形的,为了使其为线形的,将两串念珠放在同一字符串str中即可,此时str长度为2*len.
下面以求left_r,left_b为例:

left_r[0]=left_b[0]=0
For i from 1 to 2*len-1

If     str[i]='r',

left_r[i]=left_r[i-1]+1

left_b[i]=0

If     str[i]='b',

left_b[i]=left_b[i-1]+1

left_r[i]=0

If     str[i]='w',

left_b[i]=left_b[i-1]+1

left_r[i]=left_r[i-1]+1

同理可以求出right_r,right_b.最终输出的结果就是:

代码如下:

#include 
#include 
#include 
using namespace std;

int right_r[801],right_b[801],left_r[801],left_b[801];
string str;
int len;

int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    ifstream in("beads.in");
    ofstream out("beads.out");
    in>>len>>str;

    for(int i=0;i=0;i--)
    {
        if(str[i]=='r')
        {
            right_r[i]=right_r[i+1]+1;
            right_b[i]=0;
        }
        if(str[i]=='b')
        {
            right_b[i]=right_b[i+1]+1;
            right_r[i]=0;
        }
        if(str[i]=='w')
        {
            right_r[i]=right_r[i+1]+1;
            right_b[i]=right_b[i+1]+1;
        }
    }

    int m=0;
    for(int i=0;i<2*len;i++)
    {
        m=max(m,max(right_r[i],right_b[i])+max(left_r[i],left_b[i]));
    }

    if(m
其实这道题还有更加简洁的方法,继续留给明天.
(5)  三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300时刻(从5点开始计时,秒为单位)给他的牛挤奶,一直到1000时刻.第二个农民在700时刻开始,在 1200时刻结束.第三个农民在1500时刻开始2100时刻结束.期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时刻),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300时刻(从1200时刻到1500时刻).

你的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段.
最长的无人挤奶的时间段(从有人挤奶之后开始算起).


[解] 这题不像前面那道,真的是水题了.如果你会线段树的话,直接就能搞定它了.凑巧我不大会,而且我正好已经做过sicily 1484 校门外的树 这题了,因此直接拿了1484的代码修改了一下,过了.
#include 
#include 
#include 
#include 
#include 
using namespace std;

struct tree
{
    int x;
    int y;
}over;

vector v,temp;

int cmp(const struct tree &t1,const struct tree &t2 )
{
    if(t1.x>M;
    for(int i=0;i>over.x>>over.y;
        v.push_back(over);
    }
    sort(v.begin(),v.end(),cmp);

    over=v[0];
    temp.push_back(over);

    for(int i=1;itemp[temp.size()-1].y)
            temp.push_back(over);
        else
        {
            if(over.x<=temp[temp.size()-1].y&&over.x>=temp[temp.size()-1].x)
            {
                over.x=temp[temp.size()-1].x;
                over.y=(over.y>temp[temp.size()-1].y)?over.y:temp[temp.size()-1].y;
                temp.pop_back();
                temp.push_back(over);
            }
            else
            {
                if(over.x=temp[temp.size()-1].x)
                    {
                        temp.pop_back();
                        temp.push_back(over);
                    }
                    else
                    {
                        temp.push_back(over);
                    }
                }
            }
        }
    }

    if(temp.size()==1)
        out< max)
                max = temp[i].y-temp[i].x;
        }

        for(int i=2;i max2)
                max2 = temp[i].x-temp[i-1].y;
        }
        out<


PS: 豆瓣最近出了个豆瓣电台,好喜欢啊.对于我这种想要听歌又不清楚有什么歌可以听的人来说,豆瓣电台做得很不错.因为功能比较简单,选歌的余地很少,所以我也省去不少挑歌的时间,而且豆瓣强推的歌貌似都很合我胃口..

PS2: 老丘最近又在泡妞了..god,我的MM在哪里啊.