Bus Accepted : 49 Submit : 478 Time Limit : 1000 MS Memory Limit : 65536 KB 題目描述 小強剛來到長沙這個大城市，發現這裡有很多他老家沒有的東西，其中一個就是公交車了。小強的家到學校有很多個公交站，每個公交站都有一個英文名字。小強很喜歡坐公交車，但是他有個奇怪的要求，就是公交車的上車站和下車站的英文名字必須是首字母相同的，且不在同一個站上下車，不然小強寧願走過這個站去搭下一趟車，甚至直接走到學校。給出小強從家裡到學校的之間每一個公交站的英文名字，問如果不往回走，小強最多能搭幾次公交車？ 輸入 多組樣例，每組樣例第一行為非負整數n(n<=1000)，表示小強家裡到學校之間有n個公交站。接下來n行，每行有一個英文名字，每行不超過100字符。 輸出 對於每組樣例,輸出最多的乘坐次數。 樣例輸入 4 shaoshan erzhong shangxia dongmen 5 shaoshan shangxia ertian erzhong dongmen 樣例輸出 1 2 Source XTUCPC2013 [cpp] /* 思路參考我童鞋的 *題目大意：小強坐車，他不能在同一個站台(每個站台都以首字母區分）下車再上車，而且在一個站台上車必須下車的站台的首字母跟上車的站台必須一樣， *他可以走過所有站台，求小強能最多做多少次車？？ *解題思路：dp題，用dp[i][2]（i<=n),i表示每個站台，dp[i][0]表示走路到這個站台，dp[i][1]表示坐車到這個站台， *狀態轉移方程：dp[j][0]=max(dp[i][1],dp[i][0],dp[j][0])(0<=i<j),dp[j][1]=max(dp[i][0]+1,dp[j][1])(0<=i<j); */ #include<stdio.h> #include<string.h> int a[2000]; char s[2000]; int dp[2000][2]; int mmax(int a,int b) { return a>b?a:b; } int main() { int n,i,j; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%s",s); a[i]=s[0]-'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]=mmax(dp[i][1],dp[j][0]+1); // else//不能加else 因為也可以不坐車過這個地方 也要求dp[i][0] 否則就只求了坐車過的值了 // { www.2cto.com dp[i][0]=mmax(dp[i][0],dp[j][0]); dp[i][0]=mmax(dp[i][0],dp[j][1]); // } } int ans=0; for(i=0;i<n;i++) { ans=mmax(ans,dp[i][0]); ans=mmax(ans,dp[i][1]); } printf("%d\n",ans); } return 0; }
