首页 > 其他 > 详细

XTU1151:Bus(DP)

时间:2014-05-15 00:11:40      阅读:388      评论:0      收藏:0      [点我收藏+]

题目描述

小强刚来到长沙这个大城市,发现这里有很多他老家没有的东西,其中一个就是公交车了。小强的家到学校有很多个公交站,每个公交站都有一个英文名字。小强很喜欢坐公交车,但是他有个奇怪的要求,就是公交车的上车站和下车站的英文名字必须是首字母相同的,且不在同一个站上下车,不然小强宁愿走过这个站去搭下一趟车,甚至直接走到学校。给出小强从家里到学校的之间每一个公交站的英文名字,问如果不往回走,小强最多能搭几次公交车?

输入

多组样例,每组样例第一行为非负整数n(n<=1000),表示小强家里到学校之间有n个公交站。接下来n行,每行有一个英文名字,每行不超过100字符。

输出

对于每组样例,输出最多的乘坐次数。

样例输入

4
shaoshan
erzhong
shangxia
dongmen
5
shaoshan
shangxia
ertian
erzhong
dongmen

样例输出

1
2


Source

XTUCPC2013


简单DP


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

char s[105],a[1005];
int dp[1005][2];

int main()
{
    int n,i,j;
    while(~scanf("%d",&n))
    {
        for(i = 0; i<n; i++)
        {
            scanf("%s",s);
            a[i] = s[0];
        }
        memset(dp,0,sizeof(dp));
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<i; j++)
            {
                if(a[i] == a[j])
                    dp[i][1] = max(dp[i][1],dp[j][0]+1);
                dp[i][0] = max(max(dp[i][0],dp[j][1]),dp[j][0]);
            }
        }
        int ans = 0;
        for(i = 0; i<n; i++)
            ans = max(ans,max(dp[i][0],dp[i][1]));
        printf("%d\n",ans);
    }

    return 0;
}


XTU1151:Bus(DP),布布扣,bubuko.com

XTU1151:Bus(DP)

原文:http://blog.csdn.net/libin56842/article/details/25837423

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!