codeforces Hill Number 数位dp

http://www.codeforces.com/gym/100827/attachments

Hill Number

Time Limits:  5000 MS   Memory Limits:  200000 KB

64-bit interger IO format:  %lld   Java class name:  Main

Description

A Hill Number is a number whose digits possibly rise and then possibly fall, but never fall and then rise.

• 12321 is a hill number.
• 101 is not a hill number.
• 1111000001111 is not a hill number.

Given an integer n, if it is a hill number, print the number of hill numbers less than it. If it is not a hill number, print -1.

Input

Input will start with a single line giving the number of test cases. Each test case will be a single positive integer on a single line, with up to 70 digits. The result will always fit into a 64-bit long.

Output

For each test case, print -1 if the input is not a hill number. Print the number of hill numbers less than the input value if the input value is a hill number.

Sample Input

5
10
55
101
1000
1234321

Output for Sample Input

10
55
-1
715
94708
 
给你一个数,问你这个是不是山峰数。所谓山峰数,就是类似于12321这种,但是可以都一样。如果是山峰数,求出比他小的所有的山峰数个数。
 
思路:
数字很大,一看就是数位dp。
dp[i][k][w],表示第i位,为数字k的时候,状态是w的个数。w有3中状态,一种递增,一种递减,一种先递增,后递减。
dp[i][k][w] = sum(dp[i-1][j][p]);
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1<<30
#define MOD 1000000007
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pi acos(-1.0)
using namespace std;
const int MAXN = ;
ll dp[MAXN][][];
int digit[MAXN];
char s[MAXN];
int ok(char s[])
{
int len = strlen(s);
int flag = ;
for(int i = ; i < len; i++){
if(s[i] > s[i-] && flag){
return ;
}
else if(s[i] < s[i-] && !flag){
flag = ;
}
}
return ;
}
ll dfs(int len,int w,int ismax,int pa)
{
if(len == )return ;
if(!ismax && dp[len][pa][w]){//第i位 为pa数字 状态为w的时候的个数
return dp[len][pa][w];
}
ll ans = ;
ll fans = ;
int maxv = ismax ? digit[len] : ;
for(int i = ; i <= maxv; i++){
if(w == ){
if(i >= pa){
ans += dfs(len-,,ismax && i == maxv,i);
}
else {
ans += dfs(len-,,ismax && i == maxv,i);
}
}
else if(w == ){
if(i > pa)continue;
else {
ans += dfs(len-,,ismax && i == maxv,i);
}
}
else if(w == ) {
if(i > pa)continue;
else {
ans += dfs(len-,,ismax && i == maxv,i);
}
}
}
if(!ismax)dp[len][pa][w] = ans;
return ans;
}
void solve()
{
if(!ok(s)){
printf("-1\n");
return ;
}
int len = ;
memset(dp,,sizeof(dp));
for(int i = strlen(s) - ; i >= ; i--){
digit[++len] = s[i] - '';
}
printf("%lld\n",dfs(len,,,-) - );
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s);
solve();
}
return ;
}
上一篇:Codeforces 235E Number Challenge


下一篇:【宽搜】Vijos P1206 CoVH之再破难关