wangjiachi @ 2018-02-08 07:58:26
二维代码：
using namespace std; long t,n,m,a[600],b[600],c[600],d[601],dp[601][110000]; struct node{ long a,b,c,d; }e[60]; long cmp(node x,node y){ return x.by.c<y.bx.c; } int main(){ cin>>t>>n; for(long i=1;i<=n;i++){ cin>>e[i].a; } for(long i=1;i<=n;i++){ cin>>e[i].b; } for(long i=1;i<=n;i++){ cin>>e[i].c; } sort(e+1,e+1+n,cmp); for(long i=1;i<=n;i++){ for(long j=t;j>=e[i].c;j--){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-e[i].c]+e[i].a-j*e[i].b); } } long ans=-1; for(long i=1;i<=t;i++) ans=max(ans,dp[n][i]); cout<<ans; }
一维代码：
using namespace std; long t,n,m,a[600],b[600],c[600],d[601],dp[110010]; struct node{ long a,b,c,d; }e[110010]; int cmp(node x,node y){ return x.by.c>y.bx.c; } int main(){ cin>>t>>n; for(long i=1;i<=n;i++){ cin>>e[i].a; } for(long i=1;i<=n;i++){ cin>>e[i].b; } for(long i=1;i<=n;i++){ cin>>e[i].c; } sort(e+1,e+1+n,cmp); for(long i=1;i<=n;i++){ for(long j=t;j>=e[i].c;j--){ dp[j]=max(dp[j],dp[j-e[i].c]+e[i].a-j*e[i].b); } } long ans=0; for(long i=1;i<=t;i++) ans=max(ans,dp[i]); cout<<ans; }
二维50 分，一维过了
by 角边边证全等 @ 2018-02-08 08:46:48
dp[601][110000]
这会超空间
601乘110000=？？？
128MB只能开7000*7000的二维不超才怪
by zhangyinglin @ 2018-08-11 17:12:40
@wangjiachi 我的二维就可以过#include<iostream>
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-jp[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-jp[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 韩湘子 @ 2018-10-26 10:38:01
希望更丰富的展现？使用Markdown