洛谷 P1336 最佳课程选择（分组背包）

130 阅读 0 评论 86 点赞

我是靠谱客的博主乐观画板，这篇文章主要介绍洛谷 P1336 最佳课程选择（分组背包），现在分享给大家，希望可以做个参考。

题目：https://www.luogu.org/problemnew/show/P1336

思路：

转化为分组背包就简单了，和hdu 1712一模一样的。

跟选课一样，把每种课题的情况全列出来，即写1到n篇用的时间。每组只能选一个。初始化为0x3f

但是洛谷竟然不能用fill()，让我错了好半天竟然错在这。。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}