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();

 }

巴特西

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

最新文章

热门文章