dp[601][110000]
这会超空间
601乘110000=？？？
128MB只能开7000*7000的二维~~不超才怪~~
by 角边边证全等 @ 2018-02-08 08:46:48
@[wangjiachi](/space/show?uid=67418) 我的二维就可以过#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=100000+10;
ll dp[100][maxn];
struct node
{
ll a,b,t;//必须用ll
}p[100];
bool cmp(node x, node y)//一定一定要先排序
{
return x.t * y.b < y.t * x.b;
}
int main()
{
int T,n;
cin>>T>>n;
memset(p,0,sizeof(p));
memset(dp,0,sizeof(dp));
/*for(ll i=0;i<n;i++){//看好输入数据方式，坑
cin>>p[i].a>>p[i].b>>p[i].t;
}*/
for(int i = 0; i < n; i++) cin >> p[i].a;
for(int i = 0; i < n; i++) cin >> p[i].b;
for(int i = 0; i < n; i++) cin >> p[i].t;
sort(p,p+n,cmp);
ll ans=0;
/*for(int i=0;i<n;i++){//一维可以
for(int j=T;j>=p[i].t;j--){
dp[j]=max(dp[j],dp[j-p[i].t]+p[i].a-j*p[i].b);
ans=max(ans,dp[j]);
}
}*/
for(int i=0;i<n;i++){//二维也可以
for(int j=0;j<=T;j++){
if(j<p[i].t ) dp[i+1][j]=dp[i][j];
else {
ll v=p[i].a-j*p[i].b;
dp[i+1][j]=max(dp[i][j],dp[i][j-p[i].t]+v);
}
ans=max(ans,dp[i+1][j]);
}
}
cout<<ans<<endl;
return 0;
}
by zhangyinglin @ 2018-08-11 17:12:40
希望更丰富的展现？使用Markdown
by 韩湘子 @ 2018-10-26 10:38:01