首页 > 代码库 > 【贪心】超级波浪数- 10045
【贪心】超级波浪数- 10045
【贪心】超级波浪数- 10045
Time Limit: 1000MS
Memory Limit: 32768KB
波 浪数，数的大小关系就象波浪，如“14352”我们从左向右看时数的大小由小到大，然后到小，再到大，再到小，当然14253、14352、24153、 24351、34152、34251、212、121也是波浪数，但122不是波浪数，112，1221也不是波浪数，现在有一个很大的数，我们想从中选 一些数出来，组成一个波浪数，由于数很大，我们叫它超级波浪数。给定一个数，请从中选一个最长的超级波浪数。
输入：
第一行一个数（小于3000位）
输出：
一个数，最长的超级波浪数的长度。
样例：
输入
123251
输出
6
状态：F[i]表示到f[i]位的最大波浪数
状态转移方程{
If(num[i]==num[i-1])f[i]=f[i-1];如果和前面的数相同，那么波浪数不变
If(ok)f[i]=f[i-1]+1;如果位置的数是合法的，波浪数+1
If(!ok)如果不合法，波浪数不增加
}
边界f[1]=1;
1 # include<stdio.h> 2 # include<cstring> 3 # include<iostream> 4 # include<algorithm> 5 using namespace std; 6 const int maxn=3000+10; 7 int a[maxn],b[maxn],dp[maxn]; 8 char num[maxn]; 9 int main(){10 scanf("%s",num+1);11 int n=strlen(num+1);12 for(int i=2;i<=n;i++)13 if(num[i]==num[i-1]){14 a[i]=a[i-1];15 b[i]=b[i-1];16 }17 else if(num[i]>num[i-1])a[i]=a[i-1]+1;18 else if(num[i]<num[i-1])b[i]=b[i-1]+1;19 dp[1]=1;20 for(int i=2;i<=n;i++){21 if(num[i]==num[i-1])dp[i]=dp[i-1];22 else if(a[i]+b[i]==1)dp[i]=dp[i-1]+1;23 else if(a[i]+b[i]>1) dp[i]=dp[i-1];24 }25 printf("%d",dp[n]);26 return 0;27 }
【贪心】超级波浪数- 10045
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。