题意:好难表达... 分析:dp了,没什么好说的,dp[now]=min{dp[i]+dp[now-i],dp[i]+dp[now/i]且now%i==0,dp[i]+dp[j]且i^j==now;} 。不过转移的时候我的方法很暴力,不知道其他优秀的方法是怎么做的。 一些很明显的值的表达式可以预处理出来。
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <cmath>
using namespace std;
#define inf 2000000000

struct node
  {
int num;
char s[100];
}a[20010];

void ini()
  {
int i,now,j,tem,cnt;
for(i=1;i<=20000;i++) a[i].num=inf;
a[1].num=1; strcpy(a[1].s,"1"); // 1,2,3,5,7预处理出来
a[2].num=1; strcpy(a[2].s,"2");
a[3].num=1; strcpy(a[3].s,"3");
a[5].num=1; strcpy(a[5].s,"5");
a[7].num=1; strcpy(a[7].s,"7");

a[4].num=2; strcpy(a[4].s,"(2^2)"); // 4也预处理
a[6].num=1; strcpy(a[6].s,"3!"); // 预处理3到7的阶乘,因为8的阶乘已经超过20000了
a[24].num=2; strcpy(a[24].s,"(2^2)!"); // 注意阶乘的表达式外面就不用括号了,我一开始加了就wa
a[120].num=1; strcpy(a[120].s,"5!");
a[720].num=1; strcpy(a[720].s,"3!!");
a[5040].num=1; strcpy(a[5040].s,"7!");
for(now=4;now<=20000;now++) // 下面就是dp了 转移的时候很暴力
 {
if(a[now].num!=inf) continue;
tem=(int)sqrt(now+0.0);
for(i=2;i<=tem;i++)
 {
if(now%i==0)
 {
j=now/i;
if(a[i].num+a[j].num<a[now].num) // *运算
 {
a[now].num=a[i].num+a[j].num;
strcpy(a[now].s,"(");
strcat(a[now].s,a[i].s);
strcat(a[now].s,"*");
strcat(a[now].s,a[j].s);
strcat(a[now].s,")");
}
cnt=now; j=0;
while(cnt%i==0&&cnt>0)
 {
++j;
cnt/=i;
}
if(cnt==1)
 {
if(a[i].num+a[j].num<a[now].num) // ^运算
 {
a[now].num=a[i].num+a[j].num;
strcpy(a[now].s,"(");
strcat(a[now].s,a[i].s);
strcat(a[now].s,"^");
strcat(a[now].s,a[j].s);
strcat(a[now].s,")");
}
}
}
}
for(i=1;i<=now/2;i++)
 {
j=now-i;
if(a[i].num+a[j].num<a[now].num) // +运算
 {
a[now].num=a[i].num+a[j].num;
strcpy(a[now].s,"(");
strcat(a[now].s,a[i].s);
strcat(a[now].s,"+");
strcat(a[now].s,a[j].s);
strcat(a[now].s,")");
}
}
}
}

int main()
  {
ini();
int n;
while(scanf("%d",&n)!=EOF)
 {
printf("%s\n",a[n].s);
}
return 0;
}
|
|
常用链接
留言簿
随笔分类
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|