P1336 最佳课题选择【洛谷算法习题】

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

输入 #1

10 3 2 1 1 2 2 1

输出 #1

19

说明/提示

样例说明

4 44篇论文选择课题一，5 55篇论文选择课题三，剩下一篇论文选择课题二，总耗时为2 × 4 1 + 1 × 1 2 + 2 × 5 1 = 8 + 1 + 10 = 19 2\times4^1+1\times1^2+2\times5^1=8+1+10=192×41+1×12+2×51=8+1+10=19。可以证明，不存在更优的方案使耗时小于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≤200，1 ≤ m ≤ 20 1\le m\le201≤m≤20，1 ≤ A i ≤ 100 1\le A_i\le1001≤Ai​≤100，1 ≤ 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存在浮点精度误差，建议手写整数幂运算规避问题。

代码补充说明

1. 变量细节：原代码将输入的论文数n nn和课题数m mm变量名写反，但转移逻辑未出错，不影响结果。
2. 精度隐患：pow是浮点函数，计算整数幂可能出现精度偏差，推荐手动循环计算c B i c^{B_i}cBi​。
3. 边界初始化：完整写法需将DP数组初始化为极大值，再单独设置dp[0][0] = 0，保证取最小值逻辑正确。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll f[21][300],n,m,j,k,A[210],B[210],sum[10000],ans=0;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b,c,d,e,p;cin>>m>>n;for(a=1;a<=n;a++)cin>>A[a]>>B[a];for(a=1;a<=n;a++){for(b=1;b<=m;b++){for(c=0;c<=b;c++){p=A[a]*pow(c,B[a]);if(f[a][b]==0||a==1)f[a][b]=f[a-1][b-c]+p;elsef[a][b]=min(f[a-1][b-c]+p,f[a][b]);}}}cout<<f[n][m];return0;}