Code POJ - 1850

Code POJ - 1850

分析:用数位dp的方法去做,记录好last是啥,然后前面是前导零的话后一位可以选择前导零,前面不是的话后一位不能是前导零。最后判断这个数合不合法。注意一开始lead和limit都是1

code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<string>

using namespace std;

#define File(x) freopen("(x)","r",stdin)
#define pf printf
#define ull unsigned long long
#define db double
#define ll long long
#define MAXN 
#define MAXM 
#define P 
int len;
ll dp[101][10001];
string s;

ll solve(int pos,int lead,int limit,char la){ 
	if(pos==len)
	  return la!='a'-1;
	if(dp[pos][la]!=-1&&!lead&&!limit)
	  return dp[pos][la];
	ll re=0;
	char up= limit?s[pos]:'z';
	char low=la;
	for(char i=up;i>=(lead?'a'-1:la+1);i--){
		re+=solve(pos+1,lead&&i=='a'-1,limit&&i==s[pos],i);
	}
	if(!lead&&!limit)dp[pos][la]=re;
	return re;
}

int main(){
 
   cin>>s;
   memset(dp,-1,sizeof(dp));
   len=s.length();
   for(int i=1;i<len;i++){
	   if(s[i]<=s[i-1]){
		   cout<<0;
		   return 0;
	   }
   }
   cout<<solve(0,1,1,'a'-1)<<endl; 
   return 0;
}
上一篇:BootStrap框架入门


下一篇:python 领先-滞后分析 lead-lag regression