2020-2021:teams:legal_string:jxm2001:contest:edu_104

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:edu_104 [2021/02/17 19:18]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:edu_104 [2021/02/17 20:51] (当前版本)
jxm2001 [题解 2]
@@ 行 25: / 行 25: @@
 现在考虑状态数，首先 $j,k\le 5\ast\text{len}(n)$，因为可以用不超过 $5$ 个 $11\cdots 11$ 和不超过 $5$ 个 $-11\cdots 11$ 表示出 $n$ 的任意一位。
-另外设 $i$ 上界为 $T$，于是 $|\frac {i+j-k}{10}|\le max\left(\left(|\frac {i+j}{10}|,|\frac {i-k}{10}|\right)\right)\le \frac {T+5n}{10}\le T$，故 $T\le \frac {5n}9$。
+另外设 $i$ 上界为 $T$，于是 $|\frac {i+j-k}{10}|\le max\left(\left(|\frac {i+j}{10}|,|\frac {i-k}{10}|\right)\right)\le \frac {T+5\text{len}(n)}{10}\le T$，故 $T\le \frac {5\text{len}(n)}9$。
-于是总状态数为 $O(n^4)$。滚动数组滚掉一维，时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。
+于是总状态数为 $O(\text{len}(n)^4)$。滚动数组滚掉一维，时间复杂度 $O(\text{len}(n)^4)$，空间复杂度 $O(\text{len}(n)^3)$。
 注意需要给 $n$ 补上一个前导 $0$，否则最高位无法借位，会遗漏形如 $9=11-1-1$ 的情况。
@@ 行 66: / 行 66: @@
 </hidden>
+==== 题解 2 ====
+玄学做法，设 $m_i= \underbrace{11\cdots 1}_i$，从高到低考虑使用每个 $m_i$，每次操作可以认为是 $n\to n+m_i$ 或 $n\to n-m_i$。
+其中 $\text{dp}(pos,v,c,f)$ 表示考虑到 $m_{pos}$，$n$ 的高位剩下 $v\times 10^{pos}$。
+$c$ 表示所有长度不小于 $pos$ 的 $m_i$ 对第 $pos$ 位的贡献，$f$ 表示当前操作是 $+m_i$ 还是 $-m_i$。
+于是 $\text{dp}(pos,v,c,f)\gets \text{dp}(pos,v,c+f,f)$ 表示再选一个 $m_{pos}$。记 $n$ 的第 $pos$ 位最开始为 $d$。
+于是 $\text{dp}(pos,v,c,f)\gets\min(\text{dp}(pos-1,10*v+c-d,c,1),\text{dp}(pos+1,10*v+c-d,c,1))$ 表示考虑 $m_{pos+1}$。
+关于 $c$ 的上界，由题解一论证知 $|c|\le 5\ast \text{len}(n)$。
+关于 $v$，猜测需要用 $m_i$ 将 $n$ 转化为绝对值小于 $m_i$ 的数再考虑 $m_{i+1}$。
+于是 $n$ 的第 $pos$ 位最后仅允许是 $0,\pm 1$，而第 $pos$ 位的实际值为 $10*v+c-d+\lfloor\frac c{10}\rfloor$。
+新 $v$ 为 $10*v+c-d$，于是新 $v$ 不超过 $\lfloor\frac c{10}\rfloor\pm 1\sim \frac {\text{len}(n)}2$，总时间复杂度 $O(\text{len}(n)^3)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=55,MAXV=30,MAXC=255,Inf=1e9;
+int n,a[MAXN],dp[MAXN][MAXV<<1|1][MAXC<<1|1][2];
+char s[MAXN];
+int dfs(int pos,int v,int c,int f){
+	if(!pos)return v==0?0:Inf;
+	if(v<-MAXV||v>MAXV||c<-MAXC||c>MAXC)return Inf;
+	if(~dp[pos][v+MAXV][c+MAXC][f==1])return dp[pos][v+MAXV][c+MAXC][f==1];
+	int d=min(dfs(pos-1,v*10+c-a[pos-1],c,1),dfs(pos-1,v*10+c-a[pos-1],c,-1));
+	return dp[pos][v+MAXV][c+MAXC][f==1]=min(dfs(pos,v,c+f,f)+pos,d);
+}
+int main()
+{
+	scanf("%s",s);
+	n=strlen(s);
+	_for(i,0,n)a[i]=s[n-i-1]-'0';
+	a[n++]=0;
+	mem(dp,-1);
+	enter(dfs(n,0,0,1));
+	return 0;
+}
+</code>
+</hidden>

2020-2021/teams/legal_string/jxm2001/contest/edu_104.1613560734.txt.gz · 最后更改: 2021/02/17 19:18 由 jxm2001