http://acm.timus.ru/problem.aspx?space=1&num=1410
题目倒是不难,水题DP
就是题意理解起来有点困难,意思就是给你一段话,提取里面的单词
单词有小写字母和大写字母(某些单词的首部)组成 其他字符均为间隔,
而且不止一行,提取单词后,从里面选一定的单词,这些单词在原段中
不能相邻,然后让提取后所有单词总长最大
代码:
#include<iostream>
#include<stack>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<cmath> using namespace std; typedef long long ll;
typedef pair<int,int> pp;
const int INF=0x3f3f3f3f;
const int N=10003;
int d1[N],d2[N];
int a[N];
char s[N*100];
int main()
{
//freopen("data.in","r",stdin); int ln=0;
char c;
while(scanf("%c",&c)!=EOF)
s[ln++]=c; int l=0;
while(s[l]==' '&&l<ln)++l; int n=0;
int k=0;
for(int i=l;i<=ln;++i)
{
if((s[i]<='z'&&s[i]>='a')||(s[i]<='Z'&&s[i]>='A'))
++k;
else
{
if(k>0)
a[n++]=k;
k=0;
}
if(i==ln) break;
}
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
d1[0]=a[0];d2[0]=0;
for(int i=1;i<=n-1;++i)
{
d1[i]=a[i]+d2[i-1];
d2[i]=max(d1[i-1],d2[i-1]);
} cout<<max(d1[n-1],d2[n-1]);
return 0;
}