都是用贪心+排序做的,我来写个动态规划的 ^^
C++ 代码
#include<iostream>
using namespace std;
int a[105],d[105],l[105],s[105];
int cnt;
int n;
int T;
int f[1005][105];
int main() {
int i;
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
}
for(i=1;i<=n;i++){
cin>>d[i];
}
for(i=2;i<=n;i++){
cin>>l[i];
s[i]=s[i-1]+l[i];
}
f[0][0] = 0;
cin>>T;
for (int i=1;i<=T;i++) {
for (int j=1;j<=n;j++) {
for (int k=0;i-k-s[j]>=0;k++) {
f[i][j] = max(f[i][j],f[i-k-l[j]][j-1]+(2*a[j]-(k-1)*d[j])*k/2);
}
}
}
int ans = 0;
for(int i=1;i<=n;i++)
ans = max(ans,f[T][i]);
cout << ans << endl ;
return 0;
}