记录路径dp-4713-Permutation
题目链接：
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\n",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('\n'); } return 0;}