描述

Matrix67要在下個月交給老師n篇論文，論文的內容可以從m個課題中選擇。由于課題數有限，Matrix67不得不重復選擇一些課題。完成不同課題的論文所花的時間不同。具體地說，對于某個課題i，若Matrix67計劃一共寫x篇論文，則完成該課題的論文總共需要花費Ai*x^Bi個單位時間（系數Ai和指數Bi均為正整數）。給定與每一個課題相對應的Ai和Bi的值，請幫助Matrix67計算出如何選擇論文的課題使得他可以花費最少的時間完成這n篇論文。

格式

輸入格式

第一行有兩個用空格隔開的正整數n和m，分別代表需要完成的論文數和可供選擇的課題數。

以下m行每行有兩個用空格隔開的正整數。其中，第i行的兩個數分別代表與第i個課題相對應的時間系數Ai和指數Bi。

對于30%的數據，n<=10,m<=5；
對于100%的數據，n<=200，m<=20，Ai<=100，Bi<=5。

輸出格式

輸出完成n篇論文所需要耗費的最少時間。

樣例1

樣例輸入1

10 3 2 1 1 2 2 1

樣例輸出1

19

限制

各個測試點1s

提示

樣例說明：
4篇論文選擇課題一，5篇論文選擇課題三，剩下一篇論文選擇課題二，總耗時為2*4^1+1*1^2+2*5^1=8+1+10=19。可以證明，不存在更優的方案使耗時小于19。

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; long long dp[10001],c[510][10001]; int main() { int n,m,i,j,k,x,y; scanf("%d%d",&n,&m); for(i=1;i<=m;++i)//一共有m個課題 { scanf("%d%d",&x,&y); for(j=1;j<=n;++j)//要完成n個研究課題 c[i][j]=x*pow(j,y);//求出每個課題進行n次研究的耗時 } memset(dp,0x3f3f3f3f,sizeof(dp)); dp[0]=0; for(i=1;i<=m;++i)//一共有m個課題 for(j=n;j>=0;--j)//要完成n個研究課題 for(k=1;k<=j;++k)//選擇的次數 dp[j]=min(dp[j],dp[j-k]+c[i][k]); printf("%d\n",dp[n]); return 0; }

?

轉載于:https://www.cnblogs.com/jyhywh/p/6340054.html

總結

以上是生活随笔為你收集整理的vijos 1198 最佳课题选择的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。