首页 > 代码库 > ZOJ 3956 Course Selection System 背包DP
ZOJ 3956 Course Selection System 背包DP
ZOJ3956 观察数据范围， c的值非常小 只有100 所以c的和也很有限 只有50000 是否可以从这里下手？
对于某一个c的和 我们一定希望h的和最大 才有可能是最终答案。 于是有了类似背包的dp方程。
代码很简单，就不给出方程了。
//比赛的时候想得太多，都想到斜率优化上了，完全忽略了c的范围这么小！！！毕竟图样。
//一个人的面命运，当然要靠自我奋斗，但是也要考虑到历史的行程。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int LL;
const int maxn=500*100+10;
LL dp[maxn],h[501],c[501];
int main()
{freopen("t.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof(dp));
int n;
scanf("%d",&n);
LL sum=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&h[i],&c[i]);
sum+=c[i];
}
LL ans=0;
for(int i=0;i<n;i++)
for(int j=sum;j>=c[i];j--)
dp[j]=max(dp[j],dp[j-c[i]]+h[i]);
for(int j=0;j<=sum;j++)
ans=max(ans,dp[j]*dp[j]-j*dp[j]-j*j);
printf("%lld\n",ans);
}
return 0;
}
ZOJ 3956 Course Selection System 背包DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。