洛谷 P1336 最佳课程选择(分组背包)

xiaoxiao2021-02-28  14

题目: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; }
转载请注明原文地址: https://www.6miu.com/read-2800242.html

最新回复(0)