题目描述
blablabla
样例
blablabla
算法1
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =1e7+10;
int n;
int dp[N];
struct node
{
int a,b,c;
double d;
} num[110];
bool cmp(node x,node y)
{
return x.d<=y.d;
}
int main()
{
ios::sync_with_stdio(false);
int T,cnt=0;
cin>>T;
while(T--)
{
cout<<"Case #"<<++cnt<<": ";
memset(dp,0,sizeof(dp));
cin>>n;
int t=0,ans=0;
for(int i=0; i<n; i++)
{
int a,b,c;
cin>>c>>a>>b;
t+=c;
num[i]= {a,b,c,c*1.0/b};
}
sort(num,num+n,cmp);
for(int i=0;i<n;i++)
for(int j=t;j>=num[i].c;j--)
{
dp[j]=max(dp[j],dp[j-num[i].c]+max(0,num[i].a-num[i].b*(j-num[i].c)));
ans=max(ans,dp[j]);
}
cout<<ans<<endl;//有些能量石贡献为0,但又占用了时间,因此不能dp[t]
}
return 0;
}