RQNOJ 117 最佳课题选择:多重背包

题目链接: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();
}
上一篇:【转载】Python的包管理工具Pip


下一篇:luogu P1336 最佳课题选择 |背包dp