c++&oi
奇怪的乘法运算（cm）
【问题描述】
【问题描述】
下午，小家伙们对跳棋已经没有什么兴趣了，大家要求老师换一个游戏，老师说：“好玩的游戏我这还多着呢
!
不过就看谁能又快又好地回答老师的问题？”
有一个新的乘法运算符“”，我们将它的定义为：
(XY)
=
X的各位数字之和×Y的最大数字
+
Y的最小数字
例如：（
930
）
=
9
×
3
+
0
=
27
。
给定一个整数X和K，由X和运算可以组成各种不同的表达式使其运算结果为K。例如：X
=
3
K
=
7时，通过表达式：
3
(
33
)
=
3
(
3
×
3
+
3
)
=
312
=
3
×
2
+
1得到，可以证明2个运算是最少的。
现在老师要求计算出由X和运算组成的值为K的表达式最少需用多少个运算？
【数据输入】
共1行：两个整数X和K。
【数据输出】
共1行：输出最少的运算个数，如果无法得到K，则输出“Impossible
!
”（不包含双引号）
【样例】
cm.
in
cm.
out
3
12
1
【数据范围】
对100
%
的数据，
1
≤X，K≤
10
^
20
。
反复DP，和去年市赛最后一题类似。
但本题的恶心之处在于10^20
其实能生成的k的范围是很小的，约小于2000.
同时数据读入要用字符串，int64<10^1
代码
#include
<
cstdio
>
#include
<
cstring
>
#include
<
cstdlib
>
#include
<
cmath
>
int
const
maxmaxn
=
2000
;
long
long
maxn;
int
inline max(
int
a,
int
b)
{
return
a
>
b
?
a:b;}
int
inline min(
int
a,
int
b)
{
return
a
<
b
?
a:b;}
int
f[maxmaxn];
int
a[maxmaxn];
int
b[maxmaxn];
int
c[maxmaxn];
int
main()
{
maxn
=
maxmaxn
-
20
;
freopen(
"
cm.in
"
,
"
r
"
,stdin);
freopen(
"
cm.out
"
,
"
w
"
,stdout);
long
long
n;
long
long
k;
memset(f,
255
,
sizeof
(f));
//
-1这个原理请自己研究
memset(a,
0
,
sizeof
(a));
memset(b,
0
,
sizeof
(b));
memset(c,
0
,
sizeof
(c));
scanf(
"
%lld %lld
"
,
&
n,
&
k);
fclose(stdin);
if
(n
==
k)
{
printf(
"
%d
"
,
0
);
fclose(stdout);
return
0
;
}
if
(k
>
maxn)
{
printf(
"
Impossible!
"
);
fclose(stdout);
return
0
;
}
for
(
int
i
=
1
;i
<=
maxn;i
++
)
{
int
t
=
i;
c[i]
=
0x7FFFFFFF
;
while
(t)
{
int
q
=
t
%
10
;
a[i]
+=
q;
b[i]
=
max(b[i],q);
c[i]
=
min(c[i],q);
t
/=
10
;
}
}
freopen(
"
cm.in
"
,
"
r
"
,stdin);
char
s[
25
];
scanf(
"
%s
"
,s);
c[
0
]
=
0x7FFFFFFF
;
for
(
int
i
=
0
;i
<=
strlen(s)
-
1
;i
++
)
{
int
q
=
s[i]
-
'
0
'
;
a[
0
]
+=
q;
b[
0
]
=
max(b[
0
],q);
c[
0
]
=
min(c[
0
],q);
}
f[
0
]
=
0
;
fclose(stdin);
for
(;;)
{
//
反复DP
bool
flag
=
true
;
for
(
int
i
=
0
;i
<=
maxn;i
++
)
if
(f[i]
!=-
1
)
for
(
int
j
=
0
;j
<=
maxn;j
++
)
if
(f[j]
!=-
1
)
{
int
t
=
a[i]
*
b[j]
+
c[j];
if
(t
>
maxn
||
t
==
0
)
continue
;
if
((f[i]
+
f[j]
+
1
<
f[t]
&&
f[t]
>=
0
)
||
f[t]
==-
1
)
{
//
松弛
f[t]
=
f[i]
+
f[j]
+
1
;
flag
=
false
;
}
}
if
(flag)
{
//
结束
flag
=
false
;
break
;
}
}
if
(f[k]
!=-
1
)
printf(
"
%d
"
,f[k]);
else
printf(
"
Impossible!
"
);
fclose(stdout);
return
0
;
}
9！！！
posted on 2012-02-25 14:33
zyn.cpp
阅读(189)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2024年11月
>
日
一
二
三
四
五
六
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 57
文章 - 13
评论 - 11
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
(57)
2012年6月 (2)
2012年5月 (4)
2012年4月 (18)
2012年3月 (7)
2012年2月 (14)
2012年1月 (3)
2011年12月 (8)
2011年11月 (1)
文章档案
(13)
2012年2月 (1)
2011年12月 (7)
2011年11月 (1)
2011年9月 (3)
2011年8月 (1)
搜索
最新评论
1. re: 培训作业-第三周（STL&USACO+4）
评论内容较长,点击标题查看
--佛教网
2. re: 培训作业-第三周（STL&USACO+4）
评论内容较长,点击标题查看
--happem
3. re: NOIP2011解题报告
sum[i]表示前i个点的单位数?这。。，sum[i]表示i点前下车的乘客数吧？
--锐
4. re: NOIP2011解题报告
顶一下。。
--锐
5. re: 培训作业-第三周（STL&USACO+4）
@zyn.cpp
用vector暴力平衡树啊。。。
--姚京韬
阅读排行榜
1. NOIP2011普及组的第三题：瑞士轮(2619)
2. NOI LINUX 安装记(1970)
3. 随便说说状态压缩(1528)
4. 迎接初中同学——整理OI知识点（building）(803)
5. POJ 1733 (551)
评论排行榜
1. 培训作业-第三周（STL&USACO+4）(5)
2. NOIP2011普及组的第三题：瑞士轮(2)
3. POJ 1733 (1)
4. 给count-base sort正身(0)
5. 奇怪的乘法运算（cm）(0)
Powered by:
C++博客
Copyright © zyn.cpp