poj:1850 Code(组合数学?数位dp!)
2024-09-01 23:07:51
题目大意:字符的字典序依次递增才是合法的字符串,将字符串依次标号如:a-1 b-2 ... z-26 ab-27 bc-52。
为什么题解都是组合数学的...我觉得数位dp很好写啊(逃
f[pos][pre]前pos位,前一位是pre有几个满足条件的字符串,其实等同于这个字符串的序号是多少
好像数位dp的博客真没什么东西好写的...
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
char s[];
int dp[][],a[];
int dfs(int pos,int pre,bool lead,bool limit)
{
if(pos==)
if(lead)return ;else return ;
if(!limit && dp[pos][pre]!=-)return dp[pos][pre];
int up=limit?a[pos]:;
int ans=,i;
if(lead)i=pre;else i=pre+;
for(;i<=up;i++)
ans+=dfs(pos-,i,lead && i==,limit && i==a[pos]);
if(!limit)dp[pos][pre]=ans;
return ans;
}
int solve()
{
int pos=;
for(int i=;i<strlen(s)-;i++)
if(s[i]>=s[i+])return ;
for(int i=strlen(s)-;i>=;i--)
a[++pos]=s[i]-'a'+;
return dfs(pos,,,);
}
int main()
{
memset(dp,-,sizeof(dp));
scanf("%s",s);
printf("%d\n",solve());
}
最新文章
- 工业串口和网络软件通讯平台(SuperIO 2.1)更新发布
- Java:基于LinkedList实现栈和队列
- MySql中的tinying,smallint,int,bigint的类型介绍——转载
- redis的备份
- virtual box ubuntu卡在开机光标
- iOS - OC NSSet		集合
- GS界面上显示的重要参考数据
- 【M11】禁止异常流出析构方法之外
- java异常练习2
- cocoapods使用指南
- 以下是jQuery和JavaScript实现相同操作的等价代码。
- poj 1236 Network of Schools(tarjan+缩点)
- Android 使用 array.xml
- 10-UIKit(UIDatePicker、UIPickerView、UIWebView、Storyboard)
- 用大白话扯扯那";神奇";的面向对象编程思维(一)
- Java之Frame
- Struts2多文件上传原理和示例
- Linux 小知识翻译 - 「syslog」
- vs2008快捷键
- polarssl rsa &; aes 加密与解密