题目链接:https://www.rqnoj.cn/problem/117
题意:
NaCN_JDavidQ要在下个月交给老师n篇论文,论文的内容可以从m个课题中选择。
由于课题数有限,NaCN_JDavidQ不得不重复选择一些课题。
对于某个课题i,若NaCN_JDavidQ计划一共写x篇论文,则完成该课题的论文总共需要花费Ai*(x^Bi)个单位时间(系数Ai和指数Bi均为正整数)。
给定与每一个课题相对应的Ai和Bi的值,请帮助NaCN_JDavidQ计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。
题解:
转化问题:
(将对象由论文转化为课题)
有m个课题。
对于每个课题,你可以写任意篇论文。
问你恰好写完n篇论文的最小时间。
表示状态:
dp[i][j] = min time
i:考虑到第i个课题
j:已经完成了j篇论文
找出答案:
ans = dp[m][n]
如何转移:
now: dp[i][j]
dp[i+1][j+k] = min dp[i][j] + a[i]*(k^b[i])
第i个课题写了k篇论文
边界条件:
dp[0][0] = 0
others = -1
注:本题会爆int。。。
AC Code:
// state expression:
// dp[i][j] = min time
// i: considering ith project
// j: finished j papers
//
// find the answer:
// dp[m][n]
//
// transferring:
// now: dp[i][j]
// dp[i+1][j+k] = min dp[i][j] + a[i]*k^b[i]
//
// boundary:
// dp[0][0] = 0
// others = -1
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 205
#define MAX_M 25 using namespace std; int n,m;
int a[MAX_M];
int b[MAX_M];
long long dp[MAX_M][MAX_N]; void read()
{
cin>>n>>m;
for(int i=;i<m;i++)
{
cin>>a[i]>>b[i];
}
} long long quick_pow(long long n,long long k)
{
long long ans=;
while(k)
{
if(k&)
{
ans*=n;
}
n*=n;
k>>=;
}
return ans;
} void solve()
{
memset(dp,-,sizeof(dp));
dp[][]=;
for(int i=;i<m;i++)
{
for(int j=;j<=n;j++)
{
if(dp[i][j]!=-)
{
for(int k=;j+k<=n;k++)
{
long long now=dp[i][j]+a[i]*quick_pow(k,b[i]);
if(dp[i+][j+k]==- || dp[i+][j+k]>now)
{
dp[i+][j+k]=now;
}
}
}
}
}
} void print()
{
cout<<dp[m][n]<<endl;
} int main()
{
read();
solve();
print();
}