Vijos P1198 最佳课题选择

本文主要是介绍Vijos P1198 最佳课题选择，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最佳课题选择

这是一道多重背包问题

仍记得当时写出来死命debug的过程

然而最后发现没开long long导致只过两组

只考虑给当前分配多少和给前面所有的东西分配多少就可以

上代码

#include <cstdio>
#include <cstring>
#include <iostream>#define LL long longusing namespace std;const int Maxn=201;LL n,m,a[Maxn],b[Maxn],sum[Maxn],f[Maxn][Maxn];LL pow(LL x,LL n)
{LL c=1;for(int i=1;i<=n;i++)c*=x;return c;
}int main()
{memset(f,1,sizeof(f));scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++)scanf("%lld%lld",&a[i],&b[i]);for(int i=0;i<=n;i++)f[0][i]=0;for(int i=0;i<=m;i++)f[i][0]=0;for(int i=1;i<=n;i++)f[1][i]=a[1] * ( pow(i,b[1]) );for(int i=2;i<=m;i++)for(int j=1;j<=n;j++)for(int k=0;k<=j;k++){if(f[i-1][j-k] + a[i] * ( pow(k,b[i]) )<f[i][j]){sum[i]=k;f[i][j]=f[i-1][j-k] + a[i] * ( pow(k,b[i]) );}}cout<<f[m][n];
}

欢迎指出Bug

End。

这篇关于Vijos P1198 最佳课题选择的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---