【2017百度之星程序设计大赛 - 复赛】Valley Numer
2024-09-22 13:36:02
【链接】http://acm.hdu.edu.cn/showproblem.php?pid=6148
【题意】
在这里写题意
【题解】
先把1..N里面的山峰数字个数算出来->x
然后用N减去这个x就好;
这类的DP用记忆化搜索写比较好写.
参数存是否上升过,是否下降过,以及是否能枚举到9就好了.
只要出现从某一位开始能够每一位都枚举到9了.
则剩余的数字,每一位都能枚举到9;
且它的方案只有up,down,前一个数字是什么,剩余的需要枚举量这几个东西决定.
且都是固定的,通用的方案数.
【错的次数】
0
【反思】
在这了写反思
【代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0) typedef pair<int,int> pii;
typedef pair<LL,LL> pll; const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 100;
const LL MOD = 1e9+7; int T,a[N+10],len,temp[N+10];
LL dp[10][N+10][2][2];
char s[N+10]; LL dfs(int start,int cur,bool up,bool down,bool xiao){
if (cur > len) return (up&&down);
int imax = xiao?9:a[cur];
if (start!=cur && xiao && dp[temp[cur-1]][len-cur+1][up][down]!=-1)
return dp[temp[cur-1]][len-cur+1][up][down];
LL ret = 0;
rep1(i,0,imax){
temp[cur] = i;
bool ju = xiao || (i < imax);
if (i==0 && start==cur)
ret = (ret + dfs(start+1,cur+1,up,down,ju))%MOD;
else{
if (start==cur){
ret = (ret + dfs(start,cur+1,up,down,ju))%MOD;
}else {
if (up && down){
ret = (ret + dfs(start,cur+1,up,down,ju))%MOD;
}else{
if (temp[cur]==temp[cur-1]){
ret = (ret + dfs(start,cur+1,up,down,ju))%MOD;
}
if (temp[cur] > temp[cur-1]){
ret = (ret + dfs(start,cur+1,1,0,ju))%MOD;
}
if (temp[cur] < temp[cur-1]){
ret = (ret + dfs(start,cur+1,up,1,ju))%MOD;
}
}
}
}
}
if (start != cur && xiao)
dp[temp[cur-1]][len-cur+1][up][down] = ret;
return ret;
} int main(){
//Open();
//Close();
ms(dp,255);
ri(T);
while (T--){
LL init = 0;
rs(s);
len = strlen(s);
rep1(i,0,len-1)
a[i+1] = s[i]-'0';
rep1(i,1,len)
init = (init*10+a[i])%MOD;
ol((init-dfs(1,1,0,0,0)+MOD)%MOD);puts("");
}
return 0;
}
最新文章
- 安卓智能POS终端手持机PDA应用仓库出入库,移库,盘点,销售开单系统
- OpenCV2:Mat属性type,depth,step
- C和指针笔记 3.8 static关键字
- javascript photo http://www.cnblogs.com/5ishare/tag/javascript/
- 利用QObject反射实现jsonrpc
- Java 执行 SQL 脚本文件
- Cocos2d-x使用瓦片地图
- (莱昂氏unix源代码分析导读-50)LP11行式打印机
- DOM4J 读取XML配置文件进行数据库连接
- [工具] 解决sublime text运行javascript console无输出问题
- find命令笔记
- hdu 5630 Rikka with Chess
- C#中 如何执行带GO的sql 语句
- SUSE Linux 下redis 的坑
- 安卓 Android题目大全
- Python3.x 和Python2.x 区别
- OpenGL ES2.0光照
- 一套代码小程序&;Web&;Native运行的探索02
- Android细笔记--DataStorage
- CSS实现标题/段落省略效果的三剑客