题解 - Vijos

1

wang_yanheng LV 10 @ 2016-02-11 12:10:33

放代码。题解见楼下。

#include <stdio.h>
#include <string.h>
#include <math.h>

const int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 5};
char f[20][130][20]; //f[length][sum]: String
char g[20][130][20]; //second best solution
char prefix[20][20];

long long dist(char *a, char *b){
long long numA = 0, numB = 0, pow10 = 1;
for(; *a!='\0' && *b!='\0'; a++, b++){
numA = numA*10 + (*a-'0');
numB = numB*10 + (*b-'0');
pow10 *= 10;
}
if(*a == -1 || *b == -1)
return -1;
return (numB+pow10 - numA)%pow10;
}
int main(){
char str[20], tmp[20];
int length, sum, i, j, k, l, m;

scanf("%d", &length);
scanf("%s", str);

sprintf(prefix[0], "%c", str[0]);
for(i=1; i<length; i++)
sprintf(prefix[i], "%s%c", prefix[i-1], str[i]);
for(i=0, sum=0; i<length; i++)
sum += num[str[i]-'0'];

memset(f, -1, sizeof f);
memset(g, -1, sizeof g);
f[0][0][0] = 0;
for(i=0; i<length; i++){ //current length
for(j=2*i; j<=7*i; j++){ //current sum
if(f[i][j][0] < 0)
continue;
for(k=0; k<=9; k++){
m = (k+str[i]-'0')%10;
l = j+num[m];

sprintf(tmp, "%s%c", f[i][j], m+'0');
if(f[i+1][l][0] < 0 || dist(prefix[i], tmp) < dist(prefix[i], f[i+1][l])){
if(f[i+1][l][0] >= 0)
strcpy(g[i+1][l], f[i+1][l]);
strcpy(f[i+1][l], tmp);
}else if(g[i+1][l][0] < 0 || dist(prefix[i], tmp) < dist(prefix[i], g[i+1][l]))
strcpy(g[i+1][l], tmp);

if(g[i][j][0] >= 0){
sprintf(tmp, "%s%c", g[i][j], m+'0');
if(g[i+1][l][0] < 0 || dist(prefix[i], tmp) < dist(prefix[i], g[i+1][l]))
strcpy(g[i+1][l], tmp);
}
}
}
}

if(g[length][sum][0] < 0)
printf("%.0lf", pow(10, length));
else
printf("%I64d", dist(str, g[length][sum]));

return 0;
}

1

wang_yanheng LV 10 @ 2016-02-11 12:09:00

写了两天，最终成功秒杀。感觉写了一个什么都不像的算法，就把这个当作动规来看吧。整整70行。
定义如下变量：

<String> f[i][j]: 从左往右数前 i 个数，发光电子管总数为 j 时，最优解对应的数字串
<String> g[i][j]: 从左往右数前 i 个数，发光电子管总数为 j 时，次优解对应的数字串
<String> str：初始字符串
<String> prefix[i]：str 的长度为 i 的前缀串
<int> sum: 初始串发光电子管的总数
<int> length: 初始串的长度

定义如下函数：

int(x): 返回字符串 x 代表的十进制数
dist(a, b, size)：返回字符串 a 与字符串 b 的距离。要求 a 与 b 等长，长度为 size。

例如，int(0023) = 23，dist(007, 156) = 149，dist(1234, 1233) = 9999。
不难写成：dist(a, b, size) = (int(b) + 10^size - int(a)) mod 10^size

目标：
新生成一个数字串 new，使得 new 与 str 的发光电子管数目相等，且 new 距离 str 最近。递推出最优解为 f[length][sum]，次优解为 g[length][sum]。题目要求输出变换次数，也就只要输出 dist(str, g[length][sum]) 即可。（为什么要选次优解呢？后面有解释）

思路如下：
我们先考虑生成新字符串长度为 i 的前缀串 preNew[i]。显然，在发光电子管总数相同时 preNew[i] 与 prefix[i] 应该越靠近越好。比如说，初始串为 "107" ，prefix[0] = "1"，那么 preNew[0] = "2" 显然比 preNew[0] = "3" 要好。所以对于 f[i][j]，假设有一个新串 A 能做到 dist(prefix[i], A) < dist(prefix[i], f[i][j])，那么就可以更新 f[i][j]。按照这个思路就可以往下递推。
然而这样子产生的最优解一定与初始串一模一样，而这并不是我们想要的。因此这里引入了一个次优解，用以记录真正的答案。递推时，两者都需要更新。
至于为什么这么麻烦要引入次优解，而不直接把与初始串相同的情况排除掉，自己出一些数据就可以想明白。比如对于初始串 121111，这样做得到的解并不为 131111。

0

hxbks2ks LV 10 @ 2009-11-09 21:28:01

搜索加几个剪枝可过，小心‘8’。

0

zhh1993 LV 10 @ 2009-11-09 19:10:25

Accepted 有效得分：100 有效耗时：0ms

中午草草写完就走了，50分……当时只有8人过……

晚上一来，想了想——原来想简单了……稍微改了一下交上去，AC，但发现15个人过了……

T^T

简单提示一下思路：开个[1..15，-100..100]的数组f

f表示前i个数取差值j的最优解，这里的前i个指的是时钟的前i个数，差值指j的是所取的前i个数a1,a2,a3,……,ai 与最初值的前i个数b1,b2,b3,……,bi的差值和即j=(a1+a2+a3+……+ai)-(b1+b2+b3+……bi),所谓的最优解也就是转化过来的最小时间。而且我们定义这里的f所取的前i个数必须满足(a1b1) or (a2b2)……or (aibi)。另外开常量数组p[i]表示数字为i时电子管的数目。

然后是方程:f=min(f,f+y)

(x表示p[ai]-p[bi],y表示ai-bi,这里要特别注意的是f+y

0