UVa 668 Parliament

题目描述议会由NNN名代表组成要求将他们分成若干个大小互不相同的小组每天每个小组派出一名代表组成调解委员会且每天委员会的组成必须不同。议会持续工作直到无法再产生新的委员会。要求找到一种分组方案使得议会能工作最长时间并输出各组的大小升序。输入格式第一行为整数MMM表示数据集个数。每组数据包含一个整数NNN5≤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尝试将最后一个数设为jjjjlast[s−j]j \textit{last}[s-j]jlast[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]2dp[3]3\textit{dp}[3] 3dp[3]3dp[4]4\textit{dp}[4] 4dp[4]4因为444可以拆为444或131313但111无意义故直接取444。实际上从222开始。由于N≤1000N \le 1000N≤1000动态规划O(N2)O(N^2)O(N2)完全可行。回溯输出从NNN开始根据last[N]\textit{last}[N]last[N]不断减去该数直到N0N0N0得到所有拆分出的数升序输出。复杂度分析动态规划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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintPOSITIVE1,NEGATIVE-1,EQUAL0;classBigInteger{friendBigIntegeroperator*(constBigInteger,constBigInteger);friendintcompare(constBigInteger,constBigInteger);friendbooloperator(constBigInteger,constBigInteger);public:BigInteger(){};BigInteger(constint);~BigInteger(){};private:voidzeroJustify(void);staticconstintbase10000;staticconstintwidth4;intsign;vectorintdigits;};BigInteger::BigInteger(constintvalue){if(value0){signPOSITIVE;digits.push_back(0);}else{sign(value0?POSITIVE:NEGATIVE);intnumberabs(value);while(number){digits.push_back(number%base);number/base;}}zeroJustify();}voidBigInteger::zeroJustify(void){for(intidigits.size()-1;i1;i--){if(digits[i]0)digits.erase(digits.begin()i);elsebreak;}if(digits.size()1digits[0]0)signPOSITIVE;}intcompare(constBigIntegerx,constBigIntegery){if(x.signPOSITIVEy.signNEGATIVE||x.signNEGATIVEy.signPOSITIVE)return(x.signPOSITIVE?1:-1);intxDigitNumberx.digits.size()-1;for(;xDigitNumberx.digits[xDigitNumber]0;xDigitNumber--);intyDigitNumbery.digits.size()-1;for(;yDigitNumbery.digits[yDigitNumber]0;yDigitNumber--);if(xDigitNumberyDigitNumber)return(x.signPOSITIVE?1:-1);if(xDigitNumberyDigitNumber)return(x.signNEGATIVE?1:-1);for(intindexxDigitNumber;index0;index--){if(x.digits[index]y.digits[index])return(x.signPOSITIVE?1:-1);if(x.digits[index]y.digits[index])return(x.signNEGATIVE?1:-1);}return0;}booloperator(constBigIntegerx,constBigIntegery){returncompare(x,y)0;}BigIntegeroperator*(constBigIntegerx,constBigIntegery){BigInteger z;z.signx.sign*y.sign;z.digits.resize(x.digits.size()y.digits.size());fill(z.digits.begin(),z.digits.end(),0);for(inti0;iy.digits.size();i)for(intj0;jx.digits.size();j){z.digits[ij]x.digits[j]*y.digits[i];z.digits[ij1]z.digits[ij]/z.base;z.digits[ij]%z.base;}z.zeroJustify();returnz;}constBigInteger ZEROBigInteger(0),ONEBigInteger(1),TWOBigInteger(2);BigInteger product[1010];intmemo[1010];intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);for(inti0;i1001;i)product[i]ZERO;for(inti2;i4;i)product[i]BigInteger(i),memo[i]i;for(inti2;i1001;i)for(intjmemo[i]1;ji1001;j){BigInteger tproduct[i]*BigInteger(j);if(product[ij]t){product[ij]t;memo[ij]j;}}intcases;cincases;intn;for(intc1;ccases;c){cinn;vectorintsequence;while(n0){sequence.push_back(memo[n]);n-memo[n];}if(c1)cout\n;reverse(sequence.begin(),sequence.end());for(inti0;isequence.size();i){if(i)cout ;coutsequence[i];}cout\n;}return0;}总结本题通过动态规划求最大乘积拆分并记录拆分方案输出分组大小。关键点包括将问题转化为最大化乘积的互不相同正整数拆分。使用大整数存储乘积因为N1000N1000N1000时乘积极大。记录memo[s]表示最优拆分中最大的数方便回溯。该解法是动态规划在整数拆分中的典型应用适用于NNN中等规模的问题。输出时注意每组间的空行。