首页 > 代码库 > BNUOJ 52325 Increasing or Decreasing 数位dp
BNUOJ 52325 Increasing or Decreasing 数位dp
传送门:BNUOJ 52325 Increasing or Decreasing
题意:求[l,r]非递增和非递减序列的个数
思路:数位dp,dp[pos][pre][status]
- pos:处理到第几位
- pre:前一位是什么
- status:是否有前导零
递增递减差不多思路,不过他们计算的过程中像5555,444 这样的重复串会多算,所以要剪掉。个数是(pos-1)*9+digit[最高位],比如一位重复子串是:1,2,3,4...9,9个,二位重复子串:11,22,33,44,...,99,9个;同理,其他类推;
不过这个题如果dp值每算完一个[l,r]就清零,会超时。那么我们这么分析,算[l1,r1],[l2,r2]这两个区间时,dp是否真的有必要清零呢,答案是否定的,记忆化搜索的过程中记录的dp值如果计算过,那么当其他值算到他时,这个值是可以用的。具体的自己想想就好了
/************************************************************** Problem:BNUOJ 52325 Increasing or Decreasing User: youmi Language: C++ Result: Accepted Time: 380 ms Memory: 1632 KB****************************************************************///#pragma comment(linker, "/STACK:1024000000,1024000000")//#include<bits/stdc++.h>#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <stack>#include <set>#include <sstream>#include <cmath>#include <queue>#include <deque>#include <string>#include <vector>#define zeros(a) memset(a,0,sizeof(a))#define ones(a) memset(a,-1,sizeof(a))#define sc(a) scanf("%d",&a)#define sc2(a,b) scanf("%d%d",&a,&b)#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)#define scs(a) scanf("%s",a)#define sclld(a) scanf("%lld",&a)#define pt(a) printf("%d\n",a)#define ptlld(a) printf("%lld\n",a)#define rep(i,from,to) for(int i=from;i<=to;i++)#define irep(i,to,from) for(int i=to;i>=from;i--)#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define lson (step<<1)#define rson (lson+1)#define eps 1e-6#define oo 0x3fffffff#define TEST cout<<"*************************"<<endlconst double pi=4*atan(1.0);using namespace std;typedef long long ll;template <class T> inline void read(T &n){ char c; int flag = 1; for (c = getchar(); !(c >= ‘0‘ && c <= ‘9‘ || c == ‘-‘); c = getchar()); if (c == ‘-‘) flag = -1, n = 0; else n = c - ‘0‘; for (c = getchar(); c >= ‘0‘ && c <= ‘9‘; c = getchar()) n = n * 10 + c - ‘0‘; n *= flag;}ll Pow(ll base, ll n, ll mo){ ll res=1; while(n) { if(n&1) res=res*base%mo; n>>=1; base=base*base%mo; } return res;}//***************************int n;const int maxn=100000+10;const ll mod=1000000007;int digit[30];ll dp0[20][20][2];ll dp1[20][20][2];int tot=0;ll dfs0(int pos,int pre,int status,int limit){ if(pos<0) return status; if(!limit&&dp0[pos][pre][status]!=-1) return dp0[pos][pre][status]; int ed=limit?digit[pos]:9; ll res=0; if(status==0) { for(int i=0;i<=min(pre,ed);i++) { if(i==0) res+=dfs0(pos-1,10,0,limit&&(i==ed)); else res+=dfs0(pos-1,i,1,limit&&(i==ed)); } } else { for(int i=0;i<=min(ed,pre);i++) res+=dfs0(pos-1,i,status,limit&&(i==ed)); } if(!limit) dp0[pos][pre][status]=res; return res;}ll dfs1(int pos,int pre,int status,int limit){ if(pos<0) return status; if(!limit&&dp1[pos][pre][status]!=-1) return dp1[pos][pre][status]; int ed=limit?digit[pos]:9; ll res=0; for(int i=pre;i<=ed;i++) res+=dfs1(pos-1,i,status||i,limit&&(i==ed)); if(!limit) dp1[pos][pre][status]=res; return res;}void work(ll num){ tot=0; while(num) { digit[tot++]=num%10; num/=10; }}ll solve(ll num){ if(num==0) return 0; ll ans=(tot-1)*9+digit[tot-1]; ll temp=0; int tt=0; while(tt<tot) temp=temp*10+digit[tot-1],tt++; if(temp>num) ans--; return ans;}int main(){ //freopen("in.txt","r",stdin); int T_T; scanf("%d",&T_T); ones(dp0); ones(dp1); for(int kase=1;kase<=T_T;kase++) { ll num; read(num); num--; work(num); ll temp0=dfs0(tot-1,10,0,1); temp0+=dfs1(tot-1,0,0,1); temp0-=solve(num); read(num); work(num); ll temp1=dfs0(tot-1,10,0,1); temp1+=dfs1(tot-1,0,0,1); temp1-=solve(num); ptlld(temp1-temp0); } return 0;}
BNUOJ 52325 Increasing or Decreasing 数位dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。