BZOJ.1026.[SCOI2009]windy数(数位DP)

2021-04-13 14:27

阅读：700

标签：http line scanf eof mem size 影响 www. tps

题目链接

数位DP。sb了。。
前导0是有影响的，影响第一位的选择，所以要记。再记录上限，然后在没有限制时记忆化。

//820kb 4ms
#include 
#include 
#include 

int L,R,A[12],f[12][10];
bool vis[12][10];

int DFS(int pos,int las,bool lim,bool lead)
{
    if(!pos) return 1;
    if(!lim && !lead && vis[pos][las]) return f[pos][las];
    int res=0, up=lim?A[pos]:9;
    for(int i=0; iif(std::abs(i-las)>=2||lead) res+=DFS(pos-1,i,lim&&i==up,lead&&!i);//(lim&&)!
    if(!lim && !lead) vis[pos][las]=1, f[pos][las]=res;
    return res;
}
int Solve(int n)
{
    for(A[0]=0; n; n/=10) A[++A[0]]=n%10;
    memset(vis,0,sizeof vis);
    return DFS(A[0],100,1,1);
}

int main()
{
    scanf("%d%d",&L,&R);
    printf("%d",Solve(R)-Solve(L-1));
    return 0;
}

BZOJ.1026.[SCOI2009]windy数(数位DP)

标签：http line scanf eof mem size 影响 www. tps

原文地址：https://www.cnblogs.com/SovietPower/p/8975874.html

上一篇：Windows下的DOM操作

下一篇：ERROR in The node API for `babel` has been moved to `babel-core`.

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ.1026.[SCOI2009]windy数(数位DP)
文章链接：http://soscw.com/index.php/essay/75231.html

亲，登录后才可以留言！

BZOJ.1026.[SCOI2009]windy数(数位DP)

评论

热门文章

推荐文章

最新文章

置顶文章