ZJU/ZOJ 1446 Hyper-Prime Expression 解题报告

题目大意是求出用1、2、3、5、7这5个数字配合+、*、^、!这四种运算符得出表示n(n<=20000)的最简表达式（即所用数字最少）。

显然+和*两种情况的处理都比较简单，比较麻烦的是^和!的运算。不过20000内的!运算情况只有7种，因此可以对!运算进行特别处理。而对于^运算，若x^i=n，则可以用g[n,i]来记录x，通过预处理即可得到20000内所有^运算的方案。同时为了方便起见，最好将4和6的情况也预处理一下。完成了以上预处理后即可，用f[i]表示组成i所需的最少数字，则有几种情况需要处理：

• f[i]=min(f[j]+f[i-j]);
• f[i]=min(f[j]+f[i div j])(i mod j=0);
• f[i]=min(f[g[i,j]]+f[j])(g[i,j]>0);

同时在DP过程中记录下转移到当前状态的前一个状态，这样即可利用递归输出所求表达式。

1651204 2008-09-28 23:42:58 Accepted 1446 FPC 280 444 IwfWcf