题目:https://www.luogu.org/problemnew/show/P1336
思路:
转化为分组背包就简单了,和hdu 1712一模一样的。
跟选课一样,把每种课题的情况全列出来,即写1到n篇用的时间。每组只能选一个。初始化为0x3f
但是洛谷竟然不能用fill(),让我错了好半天竟然错在这。。
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int inf=0x7fffffff;
ll dp[205],c[205];
ll pow(ll x,ll y){
ll sum=1;
for(int i=1;i<=y;i++)
sum*=x;
return sum;
}
int main(){
int n,m;
cin>>n>>m;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=m;i++){
ll a,b;
cin>>a>>b;
for(int j=1;j<=n;j++)
c[j]=a*pow(j,b);
for(int j=n;j>=1;j--)
for(int k=1;k<=j;k++)
dp[j]=min(dp[j],dp[j-k]+c[k]);
}
cout<<dp[n]<<endl;
return 0;
}