显然每一位的限制独立,对于每一位求出仅限制该位下的最大数,然后求最小值即可。

假设当前要求数字$d$的答案:

考虑填数字的过程,可以看作依次考虑一个序列中的每个数,当前缀和$<0$时退出。

设$dp[i][j][k]$表示正在考虑最低的$i$位,高位部分有$j$个$d$,第$i$位能不能填$0$为$k$时,所有可能的数字形成的序列的信息。

这个信息需要维护两个值:

  • $f$:前缀和最小值。
  • $s$:总和。

显然这个信息可以进行合并。

求出答案的位数后,再从高到低逐位确定即可。

时间复杂度$O(\log^2n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100,B=10000,MAXL=25;
int cur,v[N][N][2];
struct Num{
int a[MAXL],len,fu;
Num(){len=1,fu=a[1]=0;}
void clr(){len=1,fu=a[1]=0;}
Num operator+(const Num&b)const{
Num c;
c.len=max(len,b.len)+2;
int i;
for(i=1;i<=c.len;i++)c.a[i]=0;
if(fu==b.fu){
for(i=1;i<=len;i++)c.a[i]=a[i];
for(i=1;i<=b.len;i++)c.a[i]+=b.a[i];
for(i=1;i<=c.len;i++)if(c.a[i]>=B)c.a[i+1]++,c.a[i]-=B;
while(c.len>1&&!c.a[c.len])c.len--;
c.fu=fu;
}else{
bool flag=0;
if(len==b.len){
for(i=len;i;i--)if(a[i]!=b.a[i]){
if(a[i]>b.a[i])flag=1;
break;
}
}else{
if(len>b.len)flag=1;
}
if(flag){
for(i=1;i<=len;i++)c.a[i]=a[i];
for(i=1;i<=b.len;i++)c.a[i]-=b.a[i];
for(i=1;i<=c.len;i++)if(c.a[i]<0)c.a[i+1]--,c.a[i]+=B;
while(c.len>1&&!c.a[c.len])c.len--;
c.fu=fu;
}else{
for(i=1;i<=b.len;i++)c.a[i]=b.a[i];
for(i=1;i<=len;i++)c.a[i]-=a[i];
for(i=1;i<=c.len;i++)if(c.a[i]<0)c.a[i+1]--,c.a[i]+=B;
while(c.len>1&&!c.a[c.len])c.len--;
c.fu=b.fu;
}
}
return c;
}
Num operator-(Num b)const{
b.fu^=1;
return *this+b;
}
Num operator*(const Num&b)const{
Num c;
c.len=len+b.len+2;
c.fu=fu^b.fu;
int i,j;
for(i=1;i<=c.len;i++)c.a[i]=0;
for(i=1;i<=len;i++)for(j=1;j<=b.len;j++){
c.a[i+j-1]+=a[i]*b.a[j];
if(c.a[i+j-1]>=B){
c.a[i+j]+=c.a[i+j-1]/B;c.a[i+j-1]%=B;
if(c.a[i+j]>=B)c.a[i+j+1]+=c.a[i+j]/B,c.a[i+j]%=B;
}
}
while(c.len>1&&!c.a[c.len])c.len--;
return c;
}
bool iszero()const{
return len==1&&!a[1];
}
void write(){
if(len==1&&!a[1])fu=0;
if(fu)putchar('-');
printf("%d",a[len]);
for(int i=len-1;i;i--)printf("%04d",a[i]);
}
void set(int x){
if(x<0)fu=1,x=-x;else fu=0;
if(x>=B){
len=2;
a[1]=x%B;
a[2]=x/B;
}else{
len=1;
a[1]=x;
}
}
int sgn()const{
if(iszero())return 0;
return fu==1?-1:1;
}
int cmp(const Num&b)const{
int x=sgn(),y=b.sgn();
if(x!=y)return x<y?-1:1;
if(!x)return 0;
if(x>0){
if(len!=b.len)return len<b.len?-1:1;
for(int i=len;i;i--)if(a[i]!=b.a[i])return a[i]<b.a[i]?-1:1;
return 0;
}
if(len!=b.len)return len>b.len?-1:1;
for(int i=len;i;i--)if(a[i]!=b.a[i])return a[i]>b.a[i]?-1:1;
return 0;
}
bool operator<(const Num&b)const{return cmp(b)<0;}
bool operator==(const Num&b)const{return cmp(b)==0;}
bool operator>(const Num&b)const{return cmp(b)>0;}
}ans,val[11];
struct P{
Num f,s;
P(){f.clr();s.clr();}
void clr(){f.clr();s.clr();}
P(Num _f,Num _s){f=_f,s=_s;}
P operator+(const P&b)const{return P(min(f,s+b.f),s+b.s);}
void operator+=(const P&b){*this=*this+b;}
}base,f[N][N][2];
P dfs(int x,int y,int z){
if(x==0){
P t;
t.f.set(-y);
t.s.set(-y);
return base+t;
}
if(v[x][y][z]==cur+1)return f[x][y][z];
v[x][y][z]=cur+1;
P t;
t.clr();
for(int i=z;i<10;i++)t+=dfs(x-1,y+(i==cur),0);
return f[x][y][z]=t;
}
Num solve(int _cur,int _base){
cur=_cur;
base.f.set(0);
base.s.set(_base);
int i,j,len;
P pre;
pre.clr();
for(len=1;;len++){
P now=dfs(len,0,1);
if((pre+now).f.sgn()<0)break;
pre+=now;
}
Num ans=val[0];
int sum=0;
for(i=len;i;i--)for(j=i==len?1:0;;j++){
int nowsum=sum+(j==cur);
P now=dfs(i-1,nowsum,0);
if((pre+now).f.sgn()<0){
sum=nowsum;
ans=ans*val[10]+val[j];
break;
}
pre+=now;
}
return ans;
}
int main(){
for(int i=0;i<11;i++)val[i].set(i);
for(int i=0;i<10;i++){
int x;
scanf("%d",&x);
if(i==0)ans=solve(i,x);
else ans=min(ans,solve(i,x));
}
ans=ans-val[1];
ans.write();
return 0;
}

  

最新文章

  1. Web安全相关(二):跨站请求伪造(CSRF/XSRF)
  2. Struts2标签大全
  3. 我所理解的RESTful Web API [Web标准篇]
  4. 通知、block
  5. 使用James搭建一个自己的邮箱服务器
  6. sql 数字转人民币大写函数(两种方法)
  7. Windows2008当桌面使用
  8. 如果你遇到,在IntelliJ IDEA里Ctrl+Alt+方向键用不了
  9. HDU5785 manacher+差分数组
  10. DB2常用函数:字符串函数
  11. DB2表是否存在
  12. ArcGIS API for JavaScript根据两个点坐标在地图上画线
  13. Python 实现清屏
  14. 【golang-GUI开发】qt之signal和slot(二)
  15. Python包的相对导入时出现问题解决
  16. 【Java基础】1、java中的instanceof
  17. 【Spark】Spark-架构
  18. hibernate文档头的不同版本
  19. 吴恩达-coursera-机器学习-week9
  20. grafana 的面板设置

热门文章

  1. 统一配置管理 windows linux ide maven gradle docker 【渐进式备份更新~~】
  2. EF提交插入数据catch捕获具体异常方法
  3. IDEA中debug启动tomcat报错。Error running t8:Unable to open debugger port(127.0.0.1:49225):java.net.BindException&quot;Address alread in use:JVM_Bind&quot;
  4. 天猫魔盘在 deepin-linux中的使用
  5. ccf 201903-5 317任务
  6. C++编译/运行过程中产生的各种文件
  7. html-webpack-plugin详解
  8. django_1
  9. 利用C# 窗体设计 写一个抽奖游戏
  10. 区别 chown和chmod的用法