UVa 668 Parliament-平芜编程栈

题目描述

议会由NNN名代表组成，要求将他们分成若干个大小互不相同的小组，每天每个小组派出一名代表组成调解委员会，且每天委员会的组成必须不同。议会持续工作直到无法再产生新的委员会。要求找到一种分组方案，使得议会能工作最长时间，并输出各组的大小（升序）。

输入格式

第一行为整数MMM，表示数据集个数。每组数据包含一个整数NNN（5≤N≤10005 \le N \le 10005≤N≤1000）。各组之间用一个空行分隔。

输出格式

对于每组数据，输出一行，包含若干整数，表示分组大小（升序，空格分隔）。每组输出之间用一个空行分隔。

样例

输入

2 7 31

输出

3 4 2 3 5 6 7 8

题目分析

本题本质上是一个整数拆分问题：将NNN拆分为若干个互不相同的正整数之和，使得这些数的乘积最大，并输出这些数。因为委员会每天的不同组合数等于所有小组大小的乘积（每个小组每天派出一人，不同组合数为∏sizei\prod \textit{size}_i∏sizei），要使议会工作最久，即最大化乘积。

已知结论：对于正整数拆分，若允许重复，则尽量拆分为333；但此处要求互不相同，因此应选择从222开始的一段连续整数，然后将剩余部分均匀分配到较大的数上，或者将剩余部分加到最大的数上（具体调整）。更常用的解法是动态规划。

解题思路

动态规划

设dp[s]\textit{dp}[s]dp[s]表示将总和sss拆分为互不相同的正整数时，能获得的最大乘积。同时记录last[s]\textit{last}[s]last[s]表示在最优拆分中最后一个（最大）的数，以便回溯输出方案。

转移：对于当前总和sss，尝试将最后一个数设为jjj（j>last[s−j]j > \textit{last}[s-j]j>last[s−j]以保证互不相同），则dp[s]=max⁡(dp[s],dp[s−j]×j)\textit{dp}[s] = \max(\textit{dp}[s], \textit{dp}[s-j] \times j)dp[s]=max(dp[s],dp[s−j]×j)。初始：dp[2]=2\textit{dp}[2] = 2dp[2]=2，dp[3]=3\textit{dp}[3] = 3dp[3]=3，dp[4]=4\textit{dp}[4] = 4dp[4]=4（因为444可以拆为444或1+31+31+3，但111无意义，故直接取444）。实际上从222开始。

由于N≤1000N \le 1000N≤1000，动态规划O(N2)O(N^2)O(N2)完全可行。

回溯输出

从NNN开始，根据last[N]\textit{last}[N]last[N]不断减去该数，直到N=0N=0N=0，得到所有拆分出的数，升序输出。

复杂度分析

动态规划O(N2)O(N^2)O(N2)，N≤1000N \le 1000N≤1000，约10610^6106次运算，极快。
空间复杂度O(N)O(N)O(N)。

代码实现

// Parliament// UVa ID: 668// Verdict: Accepted// Submission Date: 2017-10-26// UVa Run Time: 0.050s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintPOSITIVE=1,NEGATIVE=-1,EQUAL=0;classBigInteger{friendBigIntegeroperator*(constBigInteger&,constBigInteger&);friendintcompare(constBigInteger&,constBigInteger&);friendbooloperator<(constBigInteger&,constBigInteger&);public:BigInteger(){};BigInteger(constint&);~BigInteger(){};private:voidzeroJustify(void);staticconstintbase=10000;staticconstintwidth=4;intsign;vector<int>digits;};BigInteger::BigInteger(constint&value){if(value==0){sign=POSITIVE;digits.push_back(0);}else{sign=(value>=0?POSITIVE:NEGATIVE);intnumber=abs(value);while(number){digits.push_back(number%base);number/=base;}}zeroJustify();}voidBigInteger::zeroJustify(void){for(inti=digits.size()-1;i>=1;i--){if(digits[i]==0)digits.erase(digits.begin()+i);elsebreak;}if(digits.size()==1&&digits[0]==0)sign=POSITIVE;}intcompare(constBigInteger&x,constBigInteger&y){if(x.sign==POSITIVE&&y.sign==NEGATIVE||x.sign==NEGATIVE&&y.sign==POSITIVE)return(x.sign==POSITIVE?1:-1);intxDigitNumber=x.digits.size()-1;for(;xDigitNumber&&x.digits[xDigitNumber]==0;xDigitNumber--);intyDigitNumber=y.digits.size()-1;for(;yDigitNumber&&y.digits[yDigitNumber]==0;yDigitNumber--);if(xDigitNumber>yDigitNumber)return(x.sign==POSITIVE?1:-1);if(xDigitNumber<yDigitNumber)return(x.sign==NEGATIVE?1:-1);for(intindex=xDigitNumber;index>=0;index--){if(x.digits[index]>y.digits[index])return(x.sign==POSITIVE?1:-1);if(x.digits[index]<y.digits[index])return(x.sign==NEGATIVE?1:-1);}return0;}booloperator<(constBigInteger&x,constBigInteger&y){returncompare(x,y)<0;}BigIntegeroperator*(constBigInteger&x,constBigInteger&y){BigInteger z;z.sign=x.sign*y.sign;z.digits.resize(x.digits.size()+y.digits.size());fill(z.digits.begin(),z.digits.end(),0);for(inti=0;i<y.digits.size();i++)for(intj=0;j<x.digits.size();j++){z.digits[i+j]+=x.digits[j]*y.digits[i];z.digits[i+j+1]+=z.digits[i+j]/z.base;z.digits[i+j]%=z.base;}z.zeroJustify();returnz;}constBigInteger ZERO=BigInteger(0),ONE=BigInteger(1),TWO=BigInteger(2);BigInteger product[1010];intmemo[1010];intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);for(inti=0;i<=1001;i++)product[i]=ZERO;for(inti=2;i<=4;i++)product[i]=BigInteger(i),memo[i]=i;for(inti=2;i<=1001;i++)for(intj=memo[i]+1;j+i<=1001;j++){BigInteger t=product[i]*BigInteger(j);if(product[i+j]<t){product[i+j]=t;memo[i+j]=j;}}intcases;cin>>cases;intn;for(intc=1;c<=cases;c++){cin>>n;vector<int>sequence;while(n>0){sequence.push_back(memo[n]);n-=memo[n];}if(c>1)cout<<'\n';reverse(sequence.begin(),sequence.end());for(inti=0;i<sequence.size();i++){if(i)cout<<' ';cout<<sequence[i];}cout<<'\n';}return0;}