本文共 1205 字，大约阅读时间需要 4 分钟。
据说又是一道组合数学题，数学不好的我只想出的DP写法
注意如果输入不合法要输出0
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int maxn = 15;int lim[maxn],len;char buf[maxn],str[maxn];LL f[90][90];void getlim(char *str) { memset(lim,0,sizeof(lim)); len = strlen(str); for(int i = 0;i < len;i++) lim[i] = buf[i] - 'a' + 1;}LL dfs(int now,int prev,int bound) { LL ¬e = f[now][prev == -1 ? 0 : prev]; if(now == len - 1) { if(prev > 0) return 1; return 0; } if(!bound && note != -1) return note; int m = bound ? lim[now + 1] : 26; LL ret = 0; for(int i = prev == -1 ? 0 : prev + 1;i <= m;i++) { ret += dfs(now + 1,i == 0 ? -1 : i,bound && i == lim[now + 1]); } if(!bound) note = ret; return ret;}int main() { while(scanf("%s",buf) != EOF) { bool bad = false; len = strlen(buf); for(int i = 1;i < len;i++) if(buf[i] <= buf[i - 1]) bad = true; if(bad) { puts("0"); continue; } memset(f,-1,sizeof(f)); getlim(buf); cout << dfs(-1,-1,1) << endl; } return 0;}
转载于:https://www.cnblogs.com/rolight/p/3886862.html