P1336 最佳课题选择网页链接P1336 最佳课题选择题目描述Matrix67 要在下个月交给老师n nn篇论文论文的内容可以从m mm个课题中选择。由于课题数有限Matrix67 不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说对于某个课题i ii若 Matrix67 计划一共写x xx篇论文则完成该课题的论文总共需要花费A i × x B i A_i\times x^{B_i}Ai​×xBi​个单位时间。给定与每一个课题相对应的A i A_iAi​和B i B_iBi​的值请帮助 Matrix67 计算出如何选择论文的课题使得他可以花费最少的时间完成这n nn篇论文。输入格式第一行两个整数n nn和m mm分别代表需要完成的论文数和可供选择的课题数。接下来m mm行每行两个整数。其中第i ii行的两个数分别代表与第i ii个课题相对应的时间系数A i A_iAi​和指数B i B_iBi​。输出格式输出完成n nn篇论文所需要耗费的最少时间。输入输出样例 #1输入 #110 3 2 1 1 2 2 1输出 #119说明/提示样例说明4 44篇论文选择课题一5 55篇论文选择课题三剩下一篇论文选择课题二总耗时为2 × 4 1 1 × 1 2 2 × 5 1 8 1 10 19 2\times4^11\times1^22\times5^18110192×411×122×51811019。可以证明不存在更优的方案使耗时小于19 1919。数据规模与约定对于30 % 30\%30%的数据n ≤ 10 , m ≤ 5 n\le10,m\le5n≤10,m≤5。对于100 % 100\%100%的数据1 ≤ n ≤ 200 1\le n\le2001≤n≤2001 ≤ m ≤ 20 1\le m\le201≤m≤201 ≤ A i ≤ 100 1\le A_i\le1001≤Ai​≤1001 ≤ B i ≤ 5 1\le B_i \le 51≤Bi​≤5。解题思路本题属于资源分配类动态规划是经典的类背包模型。需将总共n nn篇论文分配给m mm个课题使总耗时最小。定义状态dp[i][j]表示使用前i ii个课题完成j jj篇论文的最小耗时。对于每个课题枚举其分配的论文数量c cc根据转移方程dp[i][j] min(dp[i][j], dp[i-1][j-c] A[i] * c^B[i])更新状态。初始时仅dp[0][0] 0其余设为无穷大。题目数据范围极小n ≤ 200 , m ≤ 20 n\le200,m\le20n≤200,m≤20三重循环的计算量很低可轻松求解。最终dp[m][n]就是完成全部论文的最少耗时。总结核心逻辑借助动态规划模拟论文分配过程枚举每个课题的选取数量不断维护最小总耗时。关键操作定义二维DP状态、计算单个课题对应篇数的耗时、逐层完成状态转移。效率保障数据规模小三重循环运算量低需注意库函数pow存在浮点精度误差建议手写整数幂运算规避问题。代码补充说明变量细节原代码将输入的论文数n nn和课题数m mm变量名写反但转移逻辑未出错不影响结果。精度隐患pow是浮点函数计算整数幂可能出现精度偏差推荐手动循环计算c B i c^{B_i}cBi​。边界初始化完整写法需将DP数组初始化为极大值再单独设置dp[0][0] 0保证取最小值逻辑正确。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll f[21][300],n,m,j,k,A[210],B[210],sum[10000],ans0;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b,c,d,e,p;cinmn;for(a1;an;a)cinA[a]B[a];for(a1;an;a){for(b1;bm;b){for(c0;cb;c){pA[a]*pow(c,B[a]);if(f[a][b]0||a1)f[a][b]f[a-1][b-c]p;elsef[a][b]min(f[a-1][b-c]p,f[a][b]);}}}coutf[n][m];return0;}