题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4713
题目大意:
题意同HDU 3092这不过这题要输出路径。
解题思路:
思路同HDU 3092。
因为n比较大,不能开二维只记录前面一个来 逆着存路径。
所以对于每个状态,把到达它的所有数都保存下来。转移的时候将前面的路径也赋值过来。
dp[i]表示表示不超过i的能分成的最大的最小公倍数的对数。少了的话用1来凑。
注意:输出的时候值小的在前面,+1成环输出。
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #define eps 1e-6 #define INF 0x3fffffff #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 10000 //三千内的质数430个 double dp[Maxn+10]; //取对数保证最小公倍数不会溢出 //dp[i]表示i能分成的最大的最小公倍数的对数 bool tmp[Maxn+10]; int pp[Maxn+10],ans[Maxn+10]; vector<int>myv[Maxn+10]; int n,cnt; void init() { cnt=0; memset(tmp,false,sizeof(tmp)); for(int i=2;i<=Maxn;i++) //素数晒选法 { if(!tmp[i]) { pp[++cnt]=i; for(int j=i*2;j<=Maxn;j+=i) tmp[j]=true; } } return ; } void solve() { memset(dp,0,sizeof(dp)); for(int i=0;i<=n;i++) myv[i].clear(); for(int i=1;i<=cnt&&pp[i]<=n;i++) { double tt=log10(pp[i]*1.0); for(int j=n;j>=pp[i];j--) //相同质数应做为一个整体考虑 { for(int k=pp[i],num=1;k<=j;k=k*pp[i],num++) if(dp[j-k]+tt*num>dp[j]) { dp[j]=dp[j-k]+tt*num; myv[j]=myv[j-k]; myv[j].push_back(k); } } } } int main() { init(); //printf("%d ",cnt); int t; scanf("%d",&t); while(t--) { scanf("%d",&n); solve(); int t=myv[n].size(); int sum=0; for(int i=0;i<t;i++) sum+=myv[n][i]; sum=n-sum; while(sum--) myv[n].push_back(1); sort(myv[n].begin(),myv[n].end()); int s=0; for(int i=0;i<myv[n].size();i++) { for(int j=1;j<myv[n][i];j++) printf("%d ",s+j+1); printf("%d",s+1); if(i!=myv[n].size()-1) putchar(' '); s+=myv[n][i]; } putchar(' '); } return 0; }