1.处理字符串
2.最长非上升子序列
3.非上升子序列的最小划分 == 上升子序列的最大长度
以下是我的代码：
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?a:b)
long deal(char s[],long begin,long end)
{
long re=0;
while(begin<end)
{
re+=s[begin++]-'0';
re*=10;
}
re+=s[end]-'0';
return re;
}
void init(char s[],long a[],long *n)
{
long begin=0,end=-1,len=strlen(s)-1,count=0;
while(end<=len)
{
while(s[++end]!=',' && s[end]!=0);
a[++count]=deal(s,begin,end-1);
begin=end+1;
}
*n=count;
}
int main()
{
char s[105];
long a[21],n,i,j,f1[21],f2[21],ans1=0,ans2=0;
scanf("%s",s);
init(s,a,&n);
for(i=1;i<=n;i++)
{
f1[i]=1;
f2[i]=1;
}
for(i=2;i<=n;i++)
for(j=i-1;j>=1;j--)
{
if(a[i]<=a[j])
f1[i]=max(f1[i],f1[j]+1);
if(a[i]>a[j])
f2[i]=max(f2[i],f2[j]+1);
}
for(i=1;i<=n;i++)
{
ans1=max(ans1,f1[i]);
ans2=max(ans2,f2[i]);
}
printf("%ld,%ld\n",ans1,ans2-1);
return 0;
}
posted on 2010-01-06 19:16
lee1r 阅读(205)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划