RQNOJ 117 最佳课题选择
题目描述
传送门
NaCN_JDavidQ要在下个月交给老师n篇论文,论文的内容可以从m个课题中选择。由于课题数有限,NaCN_JDavidQ不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说,对于某个课题i,若NaCN_JDavidQ计划一共写x篇论文,则完成该课题的论文总共需要花费Ai*x^Bi个单位时间(系数Ai和指数Bi均为正整数)。给定与每一个课题相对应的Ai和Bi的值,请帮助NaCN_JDavidQ计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。
输入格式
第一行有两个用空格隔开的正整数n和m,分别代表需要完成的论文数和可供选择的课题数。
以下m行每行有两个用空格隔开的正整数。其中,第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。
对于30%的数据,n<=10,m<=5;
对于100%的数据,n<=200,m<=20,Ai<=100,Bi<=5。
输出格式
输出完成n篇论文所需要耗费的最少时间。
样例
Input
10 3
2 1
1 2
2 1
Output
19
主要思路
首先,此题是一道dp题,但在设计方程之前,现想这样一个问题:时间怎么存?为了解决这个问题,我专门开了一个time二维数组来记录时间。其中time[i][j]表示第i个课题完成j篇论文所用的时间。只需在读入时循环枚举j,计算出来就好(建议不要用pow函数,我是手打的快速幂)。有了存储时间的方法,dp方程便不难设计:用dp[i]表示写i篇论文所用的最小时间,只需循环m个课题,再枚举当前计算的i与此时写的论文数j。
转移过程如下:
代码如下
//请看注释
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <map>
#include <stack>
#include <cstring>
using namespace std;
#define int long long//呵呵
#define INF 0x7f//呵呵
int n,m;
int dp[10005];
int tim[1005][1005];
int kuai_su_mi(int n,int m)//呵呵快速幂
{
int ans=1;
while(m)
{
if(m&1)
ans*=n;
n*=n;
m>>=1;
}
return ans;
}
#undef int//呵呵
int main(int argc, char const *argv[])//呵呵
#define int long long//呵呵
{
ios::sync_with_stdio(false);//呵呵
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
for(int j=1;j<=n;j++)//论文篇数不超过n
tim[i][j]=a*kuai_su_mi(j,b);//预处理做第i个课题中的j篇论文的时间
}
memset(dp,INF,sizeof(dp));//呵呵
dp[0]=0;//做0篇论文不需要时间
for(int k=1;k<=m;k++)//当前选到第k个课题
for(int i=n;i>0;i--)//该算dp[i]了,注意正着枚举会WA
for(int j=1;j<=i;j++)//第k个课题做了j篇论文
dp[i]=min(dp[i],dp[i-j]+tim[k][j]);
//做上一个课题时的论文数(i-j)+当前耗费的时间(time[k][j])
cout<<dp[n]<<endl;//输出
return 0;
}