题解：P13233 [GCJ 2015 Finals] Costly Binary Search
Dark_Space
·
·
题解
题解：P13233 [GCJ 2015 Finals] Costly Binary Search
:::warning{open}
本文使用了 AI 进行了润色，我保证我的贡献严格大于 AI。
:::
思路
$f2_{w,j}$ 为当状态为 $w$ 时，从字符串第 $j$ 位向右能到达的最大下标。
接下来我们对于每一个 $i$ 循环一遍。不难发现当且仅当有 $f1_{i,1} = n$ 时，状态 $i$ 是答案，此时输出即可。
接下来我们分为三步。
1. 继承上一个状态的信息。其实就是打擂台，把上一次的信息和这一次的作比较然后看那个更优。
```cpp
for(int j=1;j<=n;j++){
f1[w][j]=min(f1[w][j],f1[l][j]);
f2[w][j]=max(f2[w][j],f2[l][j]);
}
```
2. 更新左右边界的信息。这里很显然。
```cpp
for(int j=n-1;j>=1;j--){
f1[w][j]=min(f1[w][j],f1[w][j+1]);
}
for(int j=1;j<n;j++){
f2[w][j]=max(f2[w][j],f2[w][j-1]);
}
```
3. 状态转移，生成新的状态。先计算新状态 $g=(w+s_j)\mod 10$。然后更新 $f1_{g,r}$ 和 $f2_{g,l}$。
```cpp
for(int j=1;j<=n;j++){
int g=(w+s[j]-'0')%10;
int l=f1[w][j-1],r=f2[w][j+1];
f1[g][r]=min(f1[g][r],l);
f2[g][l]=max(f2[g][l],r);
}
```
这样我们就做完了。
### 代码
```cpp line-numbers
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
int T,n;
char s[1000005];
int f1[10][1000005],f2[10][1000005];
int main(){
scanf("%d",&T);
for(int cs=1;cs<=T;cs++){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=0;i<=9;i++){
for(int j=0;j<=n+1;j++){
f1[i][j]=j+1,f2[i][j]=j-1;
}
}
for(int i=1;i<=n;i++){
f1[s[i]-'0'][i]=i;
f2[s[i]-'0'][i]=i;
}
for(int i=0;1;i++){
int w=i%10;
if (f2[w][1]==n){
printf("Case #%d: %d\n",cs,i);
break;
}
int l=(i+9)%10;
if (i){
for(int j=1;j<=n;j++){
f1[w][j]=min(f1[w][j],f1[l][j]);
f2[w][j]=max(f2[w][j],f2[l][j]);
}
}
for(int j=n-1;j>=1;j--){
f1[w][j]=min(f1[w][j],f1[w][j+1]);
}
for(int j=1;j<n;j++){
f2[w][j]=max(f2[w][j],f2[w][j-1]);
}
for(int j=1;j<=n;j++){
int g=(w+s[j]-'0')%10;
int l=f1[w][j-1],r=f2[w][j+1];
f1[g][r]=min(f1[g][r],l);
f2[g][l]=max(f2[g][l],r);
}
}
}
return 0;
}
```