新十六进制

Smiling-Weeping / 2023-08-04 / 原文

Smiling & Weeping

　　　　　　　　　　　　　　　　　　　　　---- 我知觉身后有人，

　　　　　　　　　　　　　　　　　　　　　　　　在呼唤我，

　　　　　　　　　　　　　　　　　　　　　　　回头只有肆虐的风。

题目链接：码题集OJ-VIP (matiji.net)

思路：还是数位DP，不过是在其中有了筛选条件还有了一些特判，有些疲惫了(￣o￣) . z Z，话不多说，思路都在代码里面

Talk is cheap , show me the code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 500;
 5 ll dp[maxn][maxn] , num[maxn] ;
 6 char ch[maxn];
 7 bool flag;
 8 ll dfs(int pos , int last , bool lead , bool limit)
 9 {
10     ll ans = 0;
11     if(pos == 0) return 1;
12     if(!lead && !limit && dp[pos][last] != -1) return dp[pos][last];
13     int up = (limit ? num[pos] : 15);
14     for(int i = 0; i <= up; i++)
15     {
16         if(i <= last) continue; // 不符合新十六进制定义
17         if( lead && i==0 ) ans += dfs(pos-1 , -2 , true , limit && i==up);
18         else
19             ans += dfs(pos-1 , i , false , limit&&up == i);
20     }
21     if(!limit && !lead) dp[pos][last] = ans;
22     return ans;
23 }
24 inline int read_occ(char c)
25 {
26     if(isdigit(c))
27         return c-'0';
28     else
29         return c-'A'+10;
30 }
31 ll solve(int length)
32 {
33     int len = 0;
34     int ind = flag ? 2 : 1;
35     for(int i = length; i >= ind; i--)
36         num[++len] = read_occ(ch[i]);
37     memset(dp , -1 , sizeof(dp));
38     return dfs(len , -2 , true , true);
39 }
40 int main()
41 {
42     int len = 0;
43     scanf("%s",ch+1);
44     //ch[0] = '0';
45     //printf("%s\n",ch);
46     flag = ch[1]=='-' ? true : false;
47     while(ch[++len] != '\0'); len--;
48     //cout << len;
49     //  for(int i = 1; i <= 2; i++)
50     //      printf("%d\n",read_occ(ch[i]));
51     int start = 0;
52     if(ch[1] == '-') start++;
53     while(ch[++start]=='0'); start--;
54     for(int i = start; i < len; i++)
55     {
56         //if(ch[1] == '-') continue;
57         if(read_occ(ch[i]) >= read_occ(ch[i+1])){
58             printf("error\n");
59             return 0;
60         }
61     }
62     printf("%lld\n",(flag?-1:1)*(solve(len)-1));
63     return 0;
64 }